# Questions tagged [complexity-theory]

Questions related to the (computational) complexity of solving problems

5,495 questions
Filter by
Sorted by
Tagged with
4 views

### If A ∈ coNP, B ∈ NP and $NP \neq coNP$, is it possible to Karp reduce A to B?

If A $\geq_p$B and $B\in NP$, $A\in coNP$, then we can build a Turing machine $M_A$ using $M_B$ machine of B. Input: w We make a new word with a reduction function $f(w)$. Then we run $M_B$ on $f(w)$ ...
• 21
1 vote
18 views

• 63
55 views

22 views

### Tree width given path decomposition

I have a family of graphs whose path decompositions I know. Is it possible to compute the tree-width of these graphs in polynomial time?
• 516
432 views

### Undecidable problems in finite graphs

Are there any natural questions in finite graphs (or digraphs) that are undecidable?
• 516
1 vote
25 views

44 views

### Usage of matrix multiplication for distance products

This is more of a validation question, for the current best known results. On one hand, we have classical matrix multiplication. Its running time is denoted as $n^\omega$. On the other, we have ...
1 vote
35 views

• 516
64 views

### Is it known whether EXP is contained/not-contained in P/log?

Checking the complexity zoo (https://complexityzoo.net/Complexity_Zoo:P), I can only read that "if NP is contained in P/log then P = NP", so, right now, there must be no proof for EXP ...
• 479
1 vote
390 views

### If coNP ⊆ NP, does that mean coNP = NP?

I had an exam, and one of the questions was Does ZPP = BPP if coNP ⊆ ZPP. I came down to coNP ⊆ NP and went on with "then coNP = NP", am i right?
• 21
17 views

• 161
1 vote
117 views

### Why is the number of array accesses not considered in analyzing the complexity of mergesort?

I'm reading Robert Sedgewick's Algorithms and in the section about The complexity of sorting, I found the following paragraph: Proposition. Mergesort is an asymptotically optimal compare-based ...
• 147
1 vote
55 views

### Proof that $PREFIX_{TM}$ is not recognizable

We define $PREFIX_{TM}$ as the following language: $PREFIX_{TM} = \{ \text{ <M> | M is a TM, L(M)}\neq \varnothing \text{ and whenever M accepts w it accepts every prefix of w} \}$ We only ...
• 63
1 vote
46 views

### Proving that the shortest simple path problem between two vertices 𝑠 and 𝑡 in a graph with given path upperbound be positive is NP-complete

This is the same problem here but with one more condition that the sum of the distance cannot be a negative integer. The full description of the problem is: Is it possible to find a simple path (no ...
• 113
I am interested in the complexity of a special case of the boolean satisfiability problem: We are given a boolean formula, consisting only of the logical operators $\land$ and $\lor$ (that can be ...