# Tag Info

### Class of optimization problems whose decision versions are in P

This class is PO, i.e., those optimization problems where an optimal solution can be computed in polynomial time. It is known that if an optimization problem is in PO then its decision version is in P....
• 139

### Time complexity to convert a truth table to a boolean circuit

It should be polynomial for k-SAT with k not equal to 2. Otherwise it would exist a polynomial reduction from 2-SAT(that is in P) to an np-complete and than P=NP.

### Why get this P=NP? What I am doing wrong?

Both $\texttt{P}$ and $\texttt{NP}$ are subsets of the recursive function $\texttt{R}$, so by definition all $\texttt{NP}$ problems must be decidable by DTMs. But that doesn't make them equal. The ...
• 1,302

### Polynomial solutions, one less

Suppose $L = \{(G_x, Y) \mid Y$ is the maximum or minimum vertex cover of $G_x\}$. This satisfies your requirements. Now let for $G_{x_0}$, we discard $Y_a$ as the maximum vertex cover (which is all ...
• 1,435
Consider any language $L\in NP$. By definition, it has a non-determinstic TM $M$. Could you claim that: $x\in L \longleftrightarrow M$ accepts $(M,x)$? If this claim is correct, what does this imply ...