Questions tagged [time-complexity]
Time complexity of decision problems or relations among time-bounded complexity classes. (Use the [analysis-of-algorithms] tag for the time taken by particular algorithms.)
395
questions
19
votes
2
answers
2k
views
Is there a non-deterministic linear time algorithm for CNF-SAT?
The decision problem CNF-SAT can be described as follows:
Input: A boolean formula $\phi$ in conjunctive normal form.
Question: Does there exist a variable assignment that satisfies $\phi$?
I'm ...
- 5,127
12
votes
3
answers
867
views
Nontrivial problems solvable in constant time?
Constant time is the absolute low end of time complexity. One may wonder: is there anything nontrivial that can be computed in constant time? If we stick to the Turing machine model, then not much can ...
- 11.3k
19
votes
1
answer
934
views
Time complexity with irrational exponent?
Is there any natural problem in P for which the best known running time bound is of the form $O(n^\alpha)$, where $\alpha$ is an irrational constant?
- 11.3k
1
vote
0
answers
79
views
Complexity of QBF with Restrictions on Models [closed]
Do you know the complexity of the following decision problem?
Given a quantified boolean formula (QBF) $\phi$ with $2n$ free variables with $n\in\mathbb{N}$. Is there a satisfying assignment s.t. ...
- 191
3
votes
0
answers
66
views
Is this permutation-sum problem NP-complete? [duplicate]
A new, tighter tardiness bound has been found for global Earliest-Deadline-First scheduling of jobs on symmetric multiprocessors. But this bound seems to be particularly hard to compute. In particular,...
6
votes
0
answers
845
views
Is this permutation-sum problem NP-complete?
A new, tighter tardiness bound has been found for global Earliest-Deadline-First scheduling of jobs on symmetric multiprocessors. But this bound seems to be particularly hard to compute. In particular,...
1
vote
1
answer
106
views
Assignment of values for a set
Consider the following problem:
Input: the vertices of two $n$ dimensional axis-parallel cubes:
$\times_{i=1}^{n} [a_i,b_i] \subseteq [0,1]^n$ and
$\times_{i=1}^{n} [l_i,u_i] \subseteq [0,1]^n$.
...
- 253
10
votes
2
answers
349
views
The complexity of finding a Borsuk-Ulam point
The Borsuk-Ulam theorem says that for every continuous odd function $g$ from an n-sphere into Euclidean n-space, there is a point $x_0$ such that $g(x_0)=0$.
Simmons and Su (2002) describe a method ...
- 2,086
4
votes
1
answer
96
views
Approximate matching in table of integer vectors
Disclaimer: This is my first question on cstheory.stackexchange.com so please be forgiving.
I have a list of M (M is big, more than 1 million elements) vectors of integers. Each vector can contain 0-...
- 141
6
votes
2
answers
230
views
P-complete decision problems about integers
Are there any known examples of P-complete decision problems which take as input a single integer? (non-unary, as unary feels like un-naturally forcing the issue)
It feels like there are many ...
- 181
8
votes
1
answer
376
views
Hierarchy theorem for NTIME intersect coNTIME?
$\newcommand{\cc}[1]{\mathsf{#1}}$Does a theorem along the following lines hold: If $g(n)$ is a little bigger than $f(n)$, then $\cc{NTIME}(g) \cap \cc{coNTIME}(g) \neq \cc{NTIME}(f) \cap \cc{coNTIME}(...
- 1,733
3
votes
0
answers
243
views
Complexity of eigenvalue problem
Many matrix diagonalization algorithms have time complexity $\mathcal{O}(n^3)$ where $n$ is the number of columns/raws (consider only square matrices).
What is the best time lower bound it is known?
...
- 521
3
votes
2
answers
776
views
Runtime of Tucker's algorithm for generating a Eulerian circuit
What is the time complexity of Tucker's algorithm for generating a Eulerian circuit?
The Tucker's algorithm takes as input a connected graph whose vertices are all of even degree, constructs an ...
- 33
2
votes
0
answers
133
views
Complexity of Knapsack-type problem with applications to computational workflows
Consider the following problem:
Let there be a set A of $n$ items $A=\{z_1, ..., z_n\}$, and let $W$ be a strictly positive integer. Each item $z_i$ has a value $v_i$ and a weight $w_i$. Finding a ...
- 87
10
votes
0
answers
662
views
Simple path on dag with backward edges
What is the complexity of the following problem ($\in$ P? NP-hard?):
Input: a directed acyclic graph $D=(V,E)$, a set of backward edges $E'\subset V\times V$, and two distinct nodes $s$ and $t$.
...
- 1,085
-7
votes
1
answer
4k
views
Travelling sales man with Quantum Computers [closed]
I know that it takes billions of years to solve the travelling sales man when n = 25 (Number of cities). I am wondering how fast can a quantum computer solve the travelling sales man problem (for ...
- 95
7
votes
2
answers
542
views
Generalized Geography on graphs of bounded treewidth
Generalized Geography (GG) is played on a directed graph where a token is moved along arcs alternatively by two players. The vertices from which the token leaves are deleted. When a player cannot play ...
- 190
1
vote
0
answers
184
views
What is the minimal known space for polytime algorithms
Let L be a language whose minimal running time is $O(n^k)$ do we know of any bounds on the minimal amount of space necessary to compute L other than the trivial $n^k$? Are there any conjectured bounds?...
- 111
8
votes
2
answers
353
views
The hardness of generating an instance of a problem that is harder than the complexity of the resulting problem
In the movie Inception Cobb asks a asks Ariadne to design a maze that takes twice as much time to design. This lends itself to a generalized problem where we have an situation where we are resource ...
- 1,641
4
votes
0
answers
177
views
Complexity of a naive algorithm for finding the longest Fibonacci substring
I already posted this question here but I didn't receive an answer, so I'm posting it here as well :)
Given two symbols $\text{a}$ and $\text{b}$, let's define the $k$-th Fibonacci string as follows:
...
- 151
-2
votes
1
answer
987
views
Algorithm to determine if given algorithm runs in polynomial time [duplicate]
In general, the undecidability of the halting problem prohibits the general determination of an algorithm's complexity. However, I can see no reason why the halting problem prohibits one from deciding ...
2
votes
0
answers
138
views
number of iterations of this algorithm (upper bound)
Let $(A, dist)$ be a finite metric space. Consider the following "$p$-center problem": given a positive integer $p$,
find a subset $B$of $A$ such that $|B| = p$ and which minimizes the number $\max_{a ...
- 73
3
votes
1
answer
371
views
Is the following problem in P or in NP?
Given an integer $K$, a set of tasks $T=\{a_1,b_1,\dots,a_n,b_n\}$ with sequence dependent execution times $E:T \times T \rightarrow \mathbb{N}$ and precedence constraints on $T$ of the following ...
- 319
7
votes
1
answer
130
views
Quanitifier Free Presburger Arithmetic: Upper bound on solution size?
DISCLAIMER: I had originally posted this to CS.SE, but I've deleted it and moved it here, since it received little attention, and I think it is a research level question.
According to this paper, if ...
- 2,830
1
vote
0
answers
60
views
Computational complexity of Initial Value Problems of ODEs
Are there known results on computational complexity of initial value problems of ODEs? As my question may be somewhat vague, I want to mention that I'm mainly interested for results on the ...
- 161
2
votes
0
answers
104
views
Is the problem "Binary Sorted Min Sum" already known under an other name?
A computer scientist oriented toward applications gave me the following problem:
Given a positive integer $n>0$, an increasing function function $f$
and a decreasing function $g$, both defined ...
- 2,733
9
votes
1
answer
1k
views
DFA intersection algorithm for special cases
I'm interested in efficient algorithms for DFA intersection for special cases. Namely, when the DFAs to intersect obey a certain structure and/or operates on limited alphabet. Is there any source ...
user30584
8
votes
0
answers
82
views
Finding a median in a union of sets given as sorted arrays [duplicate]
You are given $k$ sorted arrays $A_1, A_2, ..., A_k$, each containing $n$ elements.
How fast can you compute the median of $A_1 \cup A_2 \cup ... \cup A_k$ ?
I have a solution running in $\Theta(k\...
- 9,438
0
votes
1
answer
222
views
Finding $x_1,x_2,...,x_k$ such that $n=x_1!+x_2!+...+x_k!$ and $k$ is minimal [closed]
Here is a problem I'm trying to solve:
Given an integer $n$ return a list $[x_1,x_2,...,x_k]$ such that $n=x_1!+x_2!+...+x_k!$ and $k$ is as low as it can be.
I'm thinking of creating a list of n ...
- 201
8
votes
0
answers
4k
views
Time complexity of a branching-and-bound algorithm
Theoretical computer scientists usually use branch-and-reduce algorithms to find exact solutions. The time complexity of such a branching algorithm is usually analyzed by the method of branching ...
- 864
2
votes
0
answers
394
views
Subset sum solver. Worth continue working on this method? [closed]
I have been working in a subset sum problem solver for some time.
The implementation is an exact/exhaustive search solver.
The variable determining the asymptomatic growth rate is just $N$ (the ...
5
votes
1
answer
3k
views
What is the worst-case runtime complexity to transform a NFA to DFA via Rabin-Scott's power set construction?
What is the worst-case runtime complexity to transform a NFA to DFA via Rabin-Scott's power set construction? Why?
Details:
http://en.wikipedia.org/wiki/Powerset_construction states that the worst-...
7
votes
0
answers
141
views
Complexity of solving vs verifying in P
Thinking of (seemingly) very different complexity of finding a solution to a NP problem and verifying it as the basis of practical cryptography, I am wondering if such separation is possible among ...
- 243
2
votes
0
answers
239
views
Recent insights on algorithms for 1D bin packing
This is just a general question on recent algorithms for the 1D bin packing problem. I just want to collect some information on this issue, so I’m grateful for any information. Especially heuristics ...
- 121
5
votes
2
answers
250
views
Fast high-dimensional K-nearest neighbors
I'm aware of this question
https://stackoverflow.com/questions/4350215/fastest-nearest-neighbor-algorithm
But it's not the same question as I'm asking. Because, Octree and its generalization are only ...
- 679
8
votes
1
answer
245
views
What's the complexity of recognizing equivalence for the following relation?
Consider the set $\mathcal{M}_{m,n}(\mathbb{Z})$ of $m$-by-$n$ matrices over, e.g., integers.
We say that two matrices $A$, $B \in \mathcal{M}_{m,n}(\mathbb{Z})$ are equivalent if $A$ can be obtained ...
- 83
-1
votes
1
answer
134
views
Using master theorem when there is a constant in the recursive term [closed]
Is it possible to use the master theorem to find the asymptotic growth of a function of the form:
$$T(n) = aT(\frac{n}{b}+c)+f(n)$$
Where $c$ is a constant. Can we safely ignore this constant and use ...
- 3
5
votes
1
answer
2k
views
Magic constant to solve NP-complete problem in polynomial time
Let's suppose that $P\ne NP$. Is that possible to solve all the instances of size $n$ of an NP-complete problem in polynomial time using some "universal magic constant" $C_n$ that has a polynomial ...
- 159
6
votes
2
answers
402
views
Complexity of finding even cuts for a graph
Given a graph $G=(V,E)$, what is known about the classical computational complexity of finding a non-trivial cut which partitions the vertices into two sets $V_a$ and $V_b$ such that every vertex in $...
- 13.6k
7
votes
3
answers
310
views
Total orders which are the transitive closure of a set in P
I am wondering if there is an example of the following form. It seems highly plausible that there should be but I am struggling to come up with one.
Consider $T \subseteq \mathbb{N}^2$, a set ...
- 434
3
votes
0
answers
60
views
Limits of parallel computing with local connections?
There are successes with an increasing numbers of individual computational units in GPUs or as processor cores. Given someone made the effort to build a huge array of processors which - however - can ...
- 147
2
votes
1
answer
832
views
Max flow: either saturate an edge or avoids
Is there a way to create a max flow graph such that it satisfies the condition that a flow either saturates an edge or completely avoids it. It can't have half its flow through one edge and half ...
- 313
0
votes
1
answer
673
views
Is the running time of Boyer-Moore linear?
With pattern length $M$, text length $N$, and alphabet $\Sigma$,
is the asymptotic running-time of Boyer-Moore $O(N/|\Sigma|)$
(even when $M$ grows larger than $|\Sigma|$)?
Are there any sublinear ...
3
votes
1
answer
1k
views
Time complexity of d-dimensional convex hull
Consider the convex hull problem in $\Re^d$:
Input: a list of $n$ points $S$ in $\Re^d$,
Output: the vertices of the convex hull of $S$.
What is the best lower bound on the time complexity of ...
user22369
2
votes
0
answers
181
views
proving speedup phenomenon does not apply to any open complexity class separations
Aaronson recently wrote a blog refuting the idea that there could be some "glitch" in the formulation of the P vs NP conjecture[1] which reminds me of this following question.
the Blum speedup ...
- 11k
13
votes
3
answers
5k
views
Examples of problems where exponential algorithms run faster than polynomial algorithms for practical sizes?
Do you know of any problems (preferably at least somewhat well known), where, for a practical problem size, an exponential algorithm runs much faster than a best-known polynomial time counterpart.
...
- 313
2
votes
2
answers
360
views
What is the asymptotic time complexity of the number of steps of "Half Or Triple Plus One" ( HOTPO)?
The "Half Or Triple Plus One" process goes as follows:
start with $x=n$ for some value of $n$
if ($x$ is odd)
$x = 3x+1$
else
$x = \frac{x}{2}$
if ($x$ > 1) goto (2)
...
13
votes
1
answer
602
views
NEXPTIME-completeness with more time for reductions
One thing that surprised me when learning about complexity theory is that for a complexity class C, we tend to define C-complete using polynomial time reductions, even when C is a very large ...
- 233
3
votes
1
answer
215
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 ...
- 131
0
votes
1
answer
850
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 axis-...
- 21