New answers tagged np
0
Let $O(G)$ be an oracle that returns the maximum cardinality of an independent set in $G$; you can implement it given your oracle using binary search.
Pick an arbitrary vertex $v$, and form a graph $G'$ by removing $v$ and all its neighbors. If $O(G') < O(G) - 1$ is false, then $v$ doesn't participate in a maximum cardinality independent set, and we try ...
1
The set $S$ consists of $12$ numbers. Hence it has $2^{12} = 4096$ subsets.
You can write a computer program that goes over all subsets, sums each of them, and determines whether the sum is $492$, in which case it prints the subset.
0
This is an answer to your first problem. For all $x \in S$, there are only two possibilities $x$ belong to some solution or $x$ does not belong to any solution. In order to check if $x$ belong to some solution, you need to call the given oracle on the updated value $t-x$. There will be two possibilities, one after calling the oracle the answer is no then ...
0
You can use the Tseytin transformation to convert a circuit to a CNF-formula in linear time (wrt to the number of gates in the circuit). The naive transformation can indeed result in exponentially larger formulas.
0
Set the size of the bag to the value you are trying to reach $t$. For each element $x \in S$ add one item to the set having both its weight and value equal to $x$. The claim is the $(S, t)$ is a yes instance of the subset sums problem if and only if the optimal value of the bag is equal to $t$ (why?).
0
NP is the class of decision problems where any instance with an answer "YES" has a proof that the answer is YES which can be checked in polynomial time. NP contains all problems that are solvable in polynomial time. Therefore there are many problems in NP with known polynomial time algorithms.
If you are talking about NP-complete problems, that's a whole ...
3
Although the shape of the problem instance is constrained, we still have total control over the polyominos themselves in any problem instance we decide to create, and we can get there by carefully messing with them.
A gangly polyomino in a double-width problem instance
Given the initial $a \times b$ problem instance, create a new instance of size $(2a+1) \...
3
P is a subset of NP, so any P language is NP as well. Also note that any deterministic machine is a non-deterministic machine where the image of the transitions function has always a size exactly equal to one. This implies that from each configuration you get a unique following configuration.
7
You haven't explained what graph isomorphism means for you, so let me assume that you mean the language of all pairs of graphs $(G_1,G_2)$ which are isomorphic.
Two graphs $G_1 = (V_1,E_1),G_2 = (V_2,E_2)$ are isomorphic if there exists a bijection $f\colon V_1 \to V_2$ such that $(x,y) \in E_1$ iff $(f(x),f(y)) \in E_2$.
You take it from here.
1
NP doesn’t look at how hard it is to find a certificate (in this case a factor), just at how hard it is to test a certificate that claims to prove the answer is “yes”.
So it doesn’t matter how hard it is to find a factor, just that given a factor of an n-bit number, you can easily verify that it is a factor in $O(n^2)$. Or a bit faster with more effort. So ...
0
It's almost always the case that problem sizes are expressed as a function of the length of the input, so a number n would be taken to be $\log n$ in length. For example, your verification would be in poly time if it ran in $O(\log^k n)$ time for some integer $k$.
Top 50 recent answers are included
