# 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.)

357 questions
Filter by
Sorted by
Tagged with
2k views

### Definition of near-linear algorithm

There are quite a lot papers describing near-linear algorithms. They are usually iterative, with linear complexity of one iteration. Others have $O(n\log^k n)$ time compexity. I'm failed to find a ...
• 131
146 views

### Testing for satisfiability of a system of linear equations over GF(2)

Consider a system linear equations in $x$, $Ax =b$, where A is an $n\times n$ matrix, and $b$ is a column vector, and all operations are over $GF(2)$. Is it easier to check satisfiability of the ...
• 271
244 views

### Complexity of #SAT for monotone DNF formulae whose hypergraph is a hypertree

A monotone DNF on variables $x_1, \ldots, x_n$ is a disjunction of clauses, each clause being a conjunction of some of the $x_1, \ldots, x_n$. The #SAT problem asks, given a monotone DNF $\Phi$, how ...
• 7,455
465 views

• 119
446 views

### Are there more polynomial time problems with complexity lower bounds?

I'm looking for more problems in $P$ with classical time complexity lower bounds. Some people might wonder how you could prove such a lower bound. See below. Exponential Lower Bounds: Claim: If ...
• 4,900
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 ...
• 4,900
805 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 ...
• 10.7k
897 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?
• 10.7k
1 vote
77 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
63 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,...
816 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
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
328 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 ...
• 1,826
91 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
222 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
345 views

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
122 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,724
1 vote
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
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,391