# Questions tagged [complexity-theory]

Questions related to the (computational) complexity of solving problems

5,084 questions
Filter by
Sorted by
Tagged with
9 views

### What is the complexity of computing logspace bounded Kolmogorov complexity?

We know that the time bounded and space bounded variants of Kolmogorov complexity are respectively NP-complete and PSPACE-complete. However, is there anything known about the complexity of the ...
1 vote
15 views

### What Complexity Class Contains $QSAT_{\log n}$?

It is known that $QSAT$ is $PSPACE$ complete, and it is known that $QSAT_i$ is $\Sigma_i$ complete for any constant $i$. However, what if we had $QSAT_{\log n}$? That is, $QSAT$ where the quantifiers ...
• 113
21 views

### The computational complexity of a variant of algorithm for the TSP (Travelling Salesman Problem)

What is the algorithm's computational complexity for a variant of the Travelling Salesman Problem, where every node must be visited at least once, meaning that a node can be visited more than once? (...
1 vote
29 views

### Understanding the Strong Exponential Time Hypothesis

Let $n$ be the number of variables in the input formula and $m$ the number of clauses. Define $s_k = \inf\{\delta : k\text{-SAT can be solved in } 2^{\delta n} \text{ time}\}$. The strong exponential ...
• 15
36 views

### Is a problem in NP if it runs in P time on a NDTM, verifiable in P on a DTM, but solution doesn’t halt on a DTM?

Say there was a decision problem which was solved optimally in polynomial time on a non-deterministic Turing machine, and verifiable in polynomial time on a deterministic TM, but would not halt when ...
39 views

18 views

### Prove that language DuplBit is in coRP

Let $A ⊂ {0, 1}^∗$ and $A ∈ coRP$. Prove that the language $DuplBit(A)$ consisting of all the results of doubling one bits in some word from $A$, also lies in $coRP$.
34 views

• 45
12 views

### Natural Problems not in P [duplicate]

From Time-Hierarchy theorem we know that there are problems that are not solvable in polynomial time. But I would like to know some natural problems that are provably not in P. Does anyone know a ...
14 views

### Equivalence of echo state networks and DFAs/NFAs

Echo state networks are theoretically equivalent to DFAs/NFAs, but how would you use an ESN to parse a regular language? Would you just feed many different input strings, some from the language and ...
1 vote