# Tag Info

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 ...
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 ...
• 159k

### 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 ...
• 2,901

### 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 ...
• 15.5k
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 ...
• 29.5k
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}$-...
• 39k
Accepted

• 277k
Accepted

### NP-Complete Proof - Using CFLP

Just set $\beta_i = 0$ instead of $q_i$.
• 6,157
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 ...
• 29.5k

### $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 ...
• 2,901
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 ...
• 29.5k

• 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 ...
• 6,157

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