New answers tagged np-complete
0
Instead of cutting corners and jumping right in to a reduction, I believe you would profit from actually stepping back and clarifying the logical basis of your argument.
Given an instance $(G, s, t)$ of HAMPATH, your reduction produces an instance $(G', s')$ of HAMCYCLE, as you have described. To prove your reduction works, you need to show:
$$(G, s, t) \in ...
3
The statement in CRLS is not wrong in any case; an algorithm that runs in $O(n)$ time also runs in $O(n^2)$ time. Of course, it would be more precise to state the running time as $O(n)$ if this were true, so why doesn't CLRS do this?
First off, this depends on the encoding chosen for $G$. If an adjacency matrix is used, a graph with $V$ vertices always has ...
1
The trick to reducing any NP problem to SAT is 1) writing a subroutine that checks the polynomially-sized certificate, 2) converting that routine to a circuit, and 3) flattening the circuit to CNF using the usual methods.
For example, to convert integer factorization to SAT, you would write a routine that multiplies two $n$-bit multipliers producing a 2$n$-...
0
Usually, there are no intuitive or enlightening reductions between problems in different problem domains.
The proof that 3SAT is NP-complete is essentially by writing a formula that says "This NP Turing machine accepts this input." For other problems about logical formulas, you can often translate the formula into a 3SAT instance. Sometimes, you can ...
4
A basic misconception about mathematics is that it is a purely formal game. Promulgated by the formalist school, we are taught that all that matters in mathematics are formal proofs. Yet in practice, completely formal proofs almost never get written; and mathematical thought has a strong informal component. In order to get further in mathematics, you need to ...
3
If we are assuming that $coNP≠𝑁𝑃$,
we can conclude that every language that is $co
NP$ complete is not in $NP$ (a contradiction to your given assumption).
Thus, every language we already know of that is $coNP$ complete, is complete as well in $coNP -NP$.
0
If the decision version can be solved in poly-time, can the optimization version be solved in poly-time as well?
This depends on how technically precise you want to be.
The most correct answer is "No". Consider an optimisation problem $OP$ for which the encoded length of the output is superpolynomial in the encoded length of the input. Clearly no algorithm ...
0
It is some sort of necro-answer to already answered and accepted question, but I want to note, that there is really easier way.
Consider you have one of inequalities like this:
$5*x_1 + 2*x_2 + 3*x_3 \leq 6$
You may easily test all no-vectors for this inequality: $(1, 1, 1)$, $(1, 1, 0)$ and $(1, 0, 1)$ others are ok.
First vector $(1, 1, 1)$ means that ...
0
Your problem is known as 3-dimensional matching, or 3DM. It is one of the 21 problems proved to be NP-hard in Karp's original paper (number 17 on his list).
0
Let's say that the numbers $a_1,\ldots,a_n$ are non-negative, and sum to $A$. They induce a probability distribution on $\{1,\ldots,n\}$, in which the probability of $i$ is $a_i/A$.
Given a partition $S_1,S_2,S_3,S_4$, let $I$ be a random variable distributed as above, and let $X$ be the index of the set to which $I$ belongs (so $X \in \{1,2,3,4\}$).
Your ...
0
NP-hardness is a category that applies to both decision problems and optimization problems. In contrast, NP-completeness is a category that applies only to decision problems.
Here are the relevant definitions:
A decision problem is in NP if it is accepted by some polynomial time nondeterministic Turing machine.
A decision problem is NP-hard if all problems ...
9
Yes. Here's a sketch of a direct proof.
If a problem is in $\mathrm{NP}$, there is a nondeterministic Turing machine $M$ that decides it, and there's a polynomial $p$ such that none of $M$'s computation paths on inputs of length $n$ take more than $p(n)$ steps. That means that a single path can't use more than $p(n)$ tape cells, so we can ...
27
Generally speaking, the following is true for any algorithm:
Suppose $A$ is an algorithm that runs in $f(n)$ time. Then $A$ could not take more than $f(n)$ space, since writing $f(n)$ bits requires $f(n)$ time.
Suppose $A$ is an algorithm that requires $f(n)$ space. Then in $2^{f(n)}$ time, $A$ can visit each of its different states, therefore can gain ...
Top 50 recent answers are included
