Skip to main content

New answers tagged

0 votes

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....
Arne's user avatar
  • 139
0 votes

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.
user3682770's user avatar
4 votes

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 ...
Knogger's user avatar
  • 1,302
2 votes

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 ...
codeR's user avatar
  • 1,435
0 votes

Acceptance of Turing Machines is NP-Hard?

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 ...
Dan D-man's user avatar
  • 524
0 votes

P vs NP problem (Student example)

To solve an instance of this problem, you need to either find one solution or prove that no solution exists. Let’s say you picked 10 items and between them they are connected to 301 other items. It is ...
gnasher729's user avatar
  • 30.6k

Top 50 recent answers are included