Time complexity of decision problems or relations among time-bounded complexity classes. (Use [tag:analysis-of-algorithms] for the time taken by particular algorithms.)

learn more… | top users | synonyms

-1
votes
0answers
40 views

Known time complexity advantage of quantum algorithms over classical algorithms [duplicate]

I know that this question may depend on how one formulates each complexity class, but in general, what time complexity advantage does quantum algorithms have over classical algorithms?
2
votes
0answers
31 views

Efficient Shamir secret sharing reconstruction

Shamir's secret sharing scheme is a well known way to convert a secret into a polynomial and distribute points in this polynomial. Some of these points can then be regrouped to reconstruct the ...
-4
votes
0answers
23 views

Solving the following recursions using the Akra-Bazzi theorem [on hold]

Can the following equations be solved using the Akra-Bazzi theorem and how? Also - I don't quite understand the h_i(x) part of the Akra-Bazzi theorem in Wikipedia. I'll appreciate an explanation. ...
-1
votes
1answer
40 views

maximum weighted 2D coverage problem by a rectangle

Let $P=\{p_1,\ldots,p_n\}$ be a set of $n$ points in a 2D plane, that is $p_i\in \mathbb{R}^2$, $\forall i=1,\ldots,n$. Each point, $p_i$, is associated with a weight, $w_i \geq 0$. Imagine a ...
11
votes
3answers
271 views

What notable automaton models have polynomially-decidable containment?

I'm trying to solve a particular problem, and I thought I might be able to solve it using automata theory. I'm wondering, what models of automata have containment decidable in polynomial time? i.e. if ...
2
votes
1answer
113 views

Is there an additive time hierarchy theorem?

I would like something like this to be true: Conjecture: There is a function $g(n)$ such that for all functions $f(n)$ (perhaps satisfying some reasonable properties, like time-constructability), ...
4
votes
3answers
111 views

Remove unneeded atoms in CNF minimalization (SAT preprocessing)

This might be a very basic question. I am interested in all atoms of a propositional formula that can be removed from a particular formula, while the derived formula has the same satisfiability ...
4
votes
3answers
361 views

Is it possible to optimize the calculation of $ax+b$ once I know $a$ and $b$?

An "algorithm" for calculating $ax+b$ would take the steps Calculate $a$ times $x$ Calculate $b$ plus the result of previous line. But if the values of $a$ and $b$ are known, can we create a more ...
8
votes
0answers
196 views

Linear space language that requires exponential time without ETH

The $\mathsf{P} \neq \mathsf{PSpace}$ conjecture means that There is a language $L \in \mathsf{DSpace}(O(n^t))$ for some $t>0$ such that for all positive integers $k$, $L$ requires ...
3
votes
1answer
66 views

Example of context-free grammar that triggers exponential behaviour without memoization in RD parsers

It is often said that memoization brings the complexity of recursive-descent parsers from exponential to polynomial. However, I had a hard time finding an example grammar that triggers the exponential ...
1
vote
1answer
81 views

Why does the construction step of Aho-Corasick take linear time in the number of nodes?

The original paper's analysis of this, as far as I can tell is this: "THEOREM 3. Algorithm 2 requires time linearly proportional to the sum of the lengths of the keywords. PROOF. Straightforward." ...
8
votes
1answer
149 views

Multidimensional arithmetic progression variant

For $\vec{d} \in \mathbb{N}^n$, let $Q(\vec{d}) \subset \mathbb{N}^n$ be the set of vertices of the $n$-dimensional cube scaled in the direction of the $i$-th coordinate by $d_i$, i.e. $Q(\vec{d} = ...
2
votes
2answers
98 views

Number of SAT checks that are needed to find all combinations of subset of boolean variables of a propositional formula

Please mind that I sometimes lack formal mathematical knowledge and English is not my first language, so I might miss the right words. Please change the tile if needed. Also, I have choosen this site ...
6
votes
1answer
194 views

Distinguishing between two coins

It is well known that the complexity of distinguishing an $\epsilon$ biased coin from a fair one is $\theta(\epsilon^{-2})$. Are there results for distinguishing a $p$ coin from a $p+\epsilon$ coin? I ...
1
vote
2answers
246 views

Lower-bound of a decision problem [closed]

What's the lower-bound of the decision problem that decides: Whether there is at least one element A[i] such that A[i] = i in a sorted array A of non-negtive integers? (An example is A = ...
0
votes
0answers
20 views

What's the official name for time-driven parallel informed sorting methods?

If you have a set $\Delta = \{A,B,C,D,E,...\}$ and you want to sort $\Delta$ based on a certain quality of the elements $\in \Delta$, then you can use a certain classification or ranking algorithm $R$ ...
0
votes
0answers
156 views

Most efficient algorithm to search an unsorted array with a very precise data structure

(I apologize in advance if this question sounds a bit practical, but I suspect it might have an interesting theoretical aspect.) I have a (large) array of data, not completely sorted, but with which ...
9
votes
0answers
181 views

Does Kannan's theorem imply that NEXPTIME^NP ⊄ P/poly?

I was reading a paper of Buhrman and Homer “Superpolynomial Circuits, Almost Sparse Oracles and the Exponential Hierarchy”. On the bottom of page 2 they remark that the results of Kannan imply that ...
8
votes
1answer
167 views

Consequences of nondeterminism speeding up deterministic computation

If $\mathsf{NP}$ contains a class of superpolynomial time problems, i.e. for some function $t \in n^{\omega(1)}$, $\mathsf{DTIME}(t) \subseteq \mathsf{NP}$, then if follows from the ...
2
votes
0answers
173 views

Does $P\neq NP$ imply any larger separation?

I've asked a similar question in cs.se, but didn't get a satisfying answer. Assuming $P\neq NP$, what can we say about the runtime of any algorithm for an $NP$-complete problem? Obviously, it means ...
4
votes
0answers
118 views

Deciding transitivity of a directed acyclic graph [duplicate]

Is there any algorithm that decides whether a given directed acyclic graph is transitive or not, in time-complexity asymptotically better than boolean matrix multiplication?
14
votes
3answers
938 views

How much time to recognize palindromes in logarithmic space?

It is well-known that palindromes can be recognized in linear time on $2$-tape Turing machines, but not on single-tape Turing machines (in which case the time needed is quadratic). The linear-time ...
4
votes
1answer
60 views

Complexity of generically inverting a class of near linear monotonic functions

Given a monotonic increasing function $f(\mathbb{N}) \rightarrow \mathbb{N}$ and a slack function $a(\mathbb{N})\rightarrow \mathbb{N}$, where $f(n) = n \pm O(a(n))$; how many calls to $f$ do we ...
2
votes
1answer
154 views

Subset Sum bounds

Are there any bounds for the subset problem with respect to the number of the terms involved in the sum and the range of the possible values?For example looking for some 2 terms whose sum equals 3 you ...
2
votes
1answer
115 views

Complexity of determining unique elements of each cycle in a permutation

It is a well known fact that a permutation is a set of cycles, and that one can find all cycles of a permutation in $O(n)$ time, where $n$ is the length of the permutation. But suppose that we know ...
7
votes
3answers
343 views

Can one automate algorithmic analysis?

Has anyone thought about the possibility of a programming language, and a compiler, such that the compiler can automatically do worst-case asymptotic analysis? The use case I have in mind is a ...
9
votes
0answers
308 views

Fundamental assumptions in complexity analysis

I am a software engineer and I need a bit of clarification. The practical performance of algorithms is usually compared against models where arithmetic and dereferencing are instantaneous, such as ...
7
votes
1answer
122 views

What is the fastest algorithm for Weighted Planar Max Cut

In 1990's, the paper Unifying Maximum Cut and Minimum Cut of a Planar Graph described an $O(n^{3/2}\log n)$-time algorithm for Weighted Planar Max Cut, a landmark in the field. Recently, this paper ...
2
votes
0answers
87 views

How is the complexity of PCA $O(\min(p^3,n^3))$?

I've been reading a paper on Sparse PCA, which is: http://stats.stanford.edu/~imj/WEBLIST/AsYetUnpub/sparse.pdf And it states that, if you have $n$ data points, each represented with $p$ features, ...
5
votes
1answer
100 views

Computational Complexity of the Divisor summatory function

The divisor function $d(n)$, is the number of $(a,b)\in\mathbb {N^+}^2$ such that $a\times b =n$. For example, $d(2)=2$ because $2=1\times 2=2\times 1$ and d(6)=4 because $6=1\times 6=2\times ...
1
vote
1answer
77 views

Calculation of Recursive Spawning

I'm reading the book Introduction to Algorithms (Cormel et al., 2009) on the chapter about multithreaded algorithms, and I'm confused about the following: We must also account for the overhead of ...
1
vote
2answers
210 views

Task Multithreading analysis for a Divide and Conquer algorithm

Suppose an algorithm that receive an input array of $n$ elements and it performs a task over each element. All tasks are independent and take $O(k)$ each (being $k$ a variable). Since all tasks are ...
11
votes
3answers
446 views

Can we compute $n$ from the bits of $3^n$ in $O(n)$ time?

I'm seeking an efficient algorithm for the problem: Input: The positive integer $3^n$ (stored as bits) for some integer $n \geq 0$. Output: The number $n$. Question: Can we compute $n$ from ...
-1
votes
1answer
417 views

Time complexity analysis of random forest and k-means?

I am working with random forest for a supervised classification problem, and I am using the k-means clustering algorithm to split the data at each node, where $n$ is the number of points, $K$ is ...
6
votes
2answers
432 views

Is there any task where classical computers outperform quantum computers?

Everybody knows that there are whole classes of problems which quantum computers are able to solve much faster (i.e. with fewer instructions) than classical computers. Is there any problem for which ...
-2
votes
2answers
514 views

Compute Time Complexity of Neural network, SVM and other classification algorithms

I would like to know what is the asymptotic time complexity analysis for general models of Back-propagation Neural Network, SVM and Maximum Entropy. Does it just depend on number of features included ...
1
vote
0answers
138 views

Time complexity of clustering based on random walk

What is the time complexity of the following algorithm (from this paper suggested by Zhou) to partition directed graph? Can I use the complexity of eigen vector computation for this purpose? The ...
3
votes
0answers
80 views

Constant time search for rod segment

(I tried to ask at SO but maybe this has more to do with the CS theory.) Suppose I have a rod which I cut to pieces. Given a point on the original rod, is there a way to find out which piece it ...
-1
votes
1answer
666 views

Flood fill vs depth first search

Is the flood fill algorithm the same as depth first search? If not, how do they differ in complexity?
20
votes
6answers
783 views

Advanced techniques for determining complexity lower bounds

Some of you may have been following this question, which was closed due to not being research level. So, I'm extracting the part of the question which is at a research level. Beyond the "simpler" ...
4
votes
0answers
270 views

How are lower bounds for computational complexity proved? [closed]

As the title says, how are lower bounds for computational complexity proved? I'm interested why it is possible to say that a certain algorithm cannot run in faster time than some lower bound. ...
1
vote
0answers
89 views

Can emptiness of reversal-bounded counter languages be decided in time polynomial to the number of counters?

I was reading this paper, about the complexity of decision problems for reversal bounded counter machines. I got to Theorem 1 on Page 6. The theorem shows that there's a log-space NTM which can ...
4
votes
1answer
164 views

state-of-the-art bit complexity of the determinant

I'm trying to understand the full bit-complexity of computing the determinant of an $n\times n$ integer matrix, with each entry represented by $M$ bits. I would like to know what is the ...
11
votes
0answers
147 views

the largest element of a matrix product

Given two matrices, I'm interested in finding the largest element of their product. I wonder if it's possible to do it significantly faster than the matrix multiplication the solution seems to ...
3
votes
1answer
121 views

Why spectral norms are used for computing the complexity of adiabatic Hamiltonian?

In the context of adiabatic quantum computation the spectral norm was first used in the first adiabatic paper by Farhi et. al. when he demonstrated the relation of it to the conventional quantum ...
5
votes
1answer
172 views

#P-Completeness of the Hosoya Index

The description from Wikipedia mentions that it is #P-Complete to compute, but there are methods. What is a layman's explanation to this?
2
votes
1answer
248 views

Finding max of two elements in linear time with restriction

I have a matrix in the following form: ...
0
votes
3answers
525 views

How can you prove that a problem is not solvable in a certain time complexity?

One of the most interesting questions in computer science is of course whether $P = NP$ or $P \neq NP$. If one wants to prove that $P \neq NP$ one can try to prove that an NPC problem is not solvable ...
15
votes
0answers
258 views

Runtime of Grover's algorithm

What is the time complexity (not query complexity) of Grover's algorithm? It seems clear to me that it is $\Omega(\log(N) \sqrt{N})$ since there are $\Omega(\sqrt{N})$ iterations and each iteration ...
11
votes
1answer
462 views

Is $\mathsf{DTIME}(n) = \mathsf{DTIME}(2n)$?

Define $\mathsf{DTIME}(f(n))$ as the class of languages that can be accepted by a (multitape) Turing machine in time $f(n) + 1$. (The "$+ 1$" is just to simplify notation and avoid confusion.) Notice ...