7 votes
Accepted

Are any "standard" complexity classes uncountably infinite?

Nonuniform complexity class P/poly is uncountable. We can just choose for each input length its own circuit, so for any subset $S \subset \mathbb{N}$ the language $L_S = \{w \colon |w| \in S \}$ is in ...
Vladimir Lysikov's user avatar
5 votes
Accepted

Is there a decidable problem that we know for sure cannot be solved in polynomial time?

It is known that P $\ne$ EXPTIME. Therefore, any EXPTIME-complete problem suffices. For instance: given a deterministic Turing machine $M$, an input $x$, and a positive integer $k$ (represented in ...
D.W.'s user avatar
  • 159k
5 votes

The SAT problem can be reduced to the complement of the halting problem?

A PTIME reduction from $\text{SAT}$ to $\overline{HALT_{TM}}$ operates as follows. On input $\varphi$, the reduction outputs $\langle M, \varphi\rangle$, where $M$ is a constant TM that operates as ...
Bader Abu Radi's user avatar
5 votes

Is 2-coloring in NL or L?

The 2-coloring problem is $\mathsf{SL}$-complete. That means that there is a logspace reduction from 2-coloring to undirected accessibility (and conversely). See this paper for some references. It was ...
Nathaniel's user avatar
  • 15.5k
5 votes
Accepted

How is P not trivially equal to ZPP?

There is an error in your reasoning. Say that $x \not\in L$. Then when you run $A(x)$ you'll get a "no" answer with certainty. However, when you run $B(x)$ you'll get a "no" with ...
Steven's user avatar
  • 29.5k
4 votes
Accepted

Unions of PSPACE-comlete problems that are PSPACE-complete?

Let $A,B\subsetneq\Sigma^*$ be $\text{PSPACE}$-complete problems for some fixed $\Sigma$ such that $A\cup B\neq\Sigma^*$ and $A\cup B\in\text{PSPACE}$. Does it follow that $A\cup B$ is $\text{PSPACE}$-...
John L.'s user avatar
  • 39k
4 votes
Accepted

The Hamiltonian cycle problem is P-hard?

The Hamiltonian cycle problem is $\mathsf{NP}$-Hard (w.r.t. poly-time reductions), that means that there is a Karp reduction from any problem in $\mathsf{NP}$ to Hamiltonian cycle. Since $\mathsf{P} \...
Steven's user avatar
  • 29.5k
3 votes

Is 2-coloring in NL or L?

Note that a graph $G$ is 2-colorable iff $G$ is bipartite iff $G$ has no odd cycle. All these equivalences are well-known and can be easily looked up. Using that, it is easy to show that the language ...
Bader Abu Radi's user avatar
3 votes
Accepted

Discrepancy in Time-Complexity of Bounded Halting Problem

I think it's simply that the Wikipedia page is a bit sloppy as it seems to be referring to $H_1$ (based on the text), even though I agree with you in that it could read as if it was talking about $H_2$...
Bernardo Subercaseaux's user avatar
3 votes

Is there such a thing as $coW[1]$-hardness?

The paper The Parameterized Complexity of Local Consistency by Gaspers and Szeider discusses coW[1]- and coW[2]-complete problems. This is maybe a starting point.
Tim Seppelt's user avatar
2 votes
Accepted

How is $\mathsf{RP\cap UP}$ not a class containing only unsatisfying languages?

The $\mathsf{RP}$ machine and the $\mathsf{UP}$ machine don't have to be the same. That is, there might be one machine which shows that $L \in \mathsf{RP}$, and another one which shows that $L \in \...
Yuval Filmus's user avatar
2 votes
Accepted

NP-Complete Proof - Using CFLP

Just set $\beta_i = 0$ instead of $q_i$.
Inuyasha Yagami's user avatar
2 votes
Accepted

The problems in the P class can be polynomially reduced to its complement and vica versa?

The claim is false. $\emptyset$ cannot be reduced to its complement $\Sigma^*$ (and vice-versa). However, if you restrict yourself to languages $L$ such that $L \not\in \{ \emptyset, \Sigma^*\}$ then ...
Steven's user avatar
  • 29.5k
2 votes

$A$ and $B$ two decision problems.If $A\le\ B$ then $\overline{B}\le\overline{A}$ is true?

The claim is false. There are several ways to show it. Note that if $\overline{B} \leq_m \overline{A}$, then $B\leq_m A$ (this is what you've shown). Hence, if by contradiction the claim is true, then ...
Bader Abu Radi's user avatar
2 votes
Accepted

The SAT problem can be reduced to the complement of the halting problem?

Let $T$ be a fixed Turing machine that decides SAT. From $T$ it is easy to construct a Turing machine $T'$ that takes SAT instance $x$ as input and halts iff $T(x)$ rejects. In other words, given a ...
Steven's user avatar
  • 29.5k
2 votes

Is there an NP-hard problem that is polynomially reducible to its complement, and whose complement is polynomially reducible to the problem?

Take any NP-hard problem $A \subseteq \{0,1\}^*$. Now let $\langle A, \overline{A}\rangle := \{0w \mid w \in A\} \cup \{1w \mid w \notin A\}$. Clearly, $A$ is polytime reducible to $\langle A, \...
Arno's user avatar
  • 3,075
1 vote
Accepted

NP, NP-Hard and NP-Complete

If a problem S is NP-Complete and we know that a problem Q is polynomial time reducible to S. Does that mean that Q belongs to NP? Yes. "$S$ is NP-complete" means two things: $S$ is NP, and ...
Jean Abou Samra's user avatar
1 vote

$A$ and $B$ two decision problems.If $A\le\ B$ then $\overline{B}\le\overline{A}$ is true?

No. Take $A = \emptyset$ and $B = \{0\}$. A reduction $f$ from $A$ to $B$ is the function $f(x) = \varepsilon$ since $x \not\in A$ (regardless of the choice of $x$) and $\varepsilon\not\in B$. However ...
Steven's user avatar
  • 29.5k
1 vote
Accepted

We know that there is an algorithm for a problem that decides it in $\Omega(2^n)$ time. We know that it is not in P class, or we cannot decide?

Well, there is a sorting algorithm that takes $\Omega(n!)$ steps on average: Create a random permutation of your data, check whether the resulting array is sorted, and repeat until it is sorted. But ...
gnasher729's user avatar
1 vote

Using time hierarchy theorem to show $Time(n^7)$ strictly contained in P

By the time hierarchy theorem, if $f$ and $g$ are time-constructible functions and $f(n) \log f(n) = o(g(n))$ then $\mathsf{DTIME}( f(n) ) \subsetneq \mathsf{DTIME}(g(n))$. From your question you seem ...
Steven's user avatar
  • 29.5k
1 vote

Complexity of this variant of #Positive 2-SAT #P-complete?

The problem is in P for any fixed $k$. The clauses shouldn't need to be all positive, either. For the positive example, let's say we choose from sets $A$, $B$ and $C$ (it doesn't really matter). For ...
Highheath's user avatar
  • 1,046
1 vote
Accepted

$NL$ Leaf languages and $PSPACE$

You are omitting some very important details. In the exercise, the Turing machine $N$ is required to halt on all its possible computation paths using exactly $p(n)$ steps, where $n$ is the size of the ...
Steven's user avatar
  • 29.5k
1 vote
Accepted

Integrality gap and complexity classes

The question is incorrect. The integrality gap is defined for a linear programming formulation of the problem and not fundamentally for the problem. It is possible that a problem has more than one ...
Inuyasha Yagami's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible