Articles of np complete

How can we show that 3-dimensional matching $\le_p$ exact cover?

In exact cover, we’re given some universe of objects and subsets on those objects, and we want to know if a set of the subsets can cover the whole universe such that all selected subsets are pairwise disjoint. I’m wondering how we can show 3-dimensional matching $\le_p$ exact cover. Given an instance of the 3-dimensional […]

Proof that SAT is NPC

I am not really sure I understand the idea behind Cook theorem (it says that SAT is a NP-complete problem). I read the proof with all its parts corresponding to the Turing machine TM solving it (TM is in a single state at any given time, only single cell is read by the head of […]

Confusion related to the definition of NP problems

I have this confusion related to the definition of NP problems. According to wikipedia Intuitively, NP is the set of all decision problems for which the instances where the answer is “yes” have efficiently verifiable proofs of the fact that the answer is indeed “yes”. More precisely, these proofs have to be verifiable in polynomial […]

Is half-filled magic square problem NP-complete?

Here is the problem: We have a square with some numbers from 1..N in some cells. It’s needed to determine if it can be completed to a magic square. Examples: 2 _ 6 2 7 6 _ 5 1 >>> 9 5 1 4 3 _ 4 3 8 7 _ _ 9 _ _ […]

A graph problem

Consider the following graph problem. For a number $K$ and a set $\mathcal{K} = \{ 1, \ldots,K\}$, we have a set of vertices $V_k^s$ for all $s \subset \mathcal{K} \setminus \{k\}$, $s$ is not empty and for all $k$. For example, if $K =2$, we have $V_1^{\{2\}}$ and $V_2^{\{1\}}$. if $K =3$, we have $V_1^{\{2,3\}}$, […]

The Practical Implication of P vs NP Problem

Although whether $$ P = NP $$ is important from theoretical computer science point of view, but I fail to see any practical implication of it. Suppose that we can prove all questions that can be verified in polynomial time have polynomial time solutions, it won’t help us in finding the actual solutions. Conversely, if […]

For two problems A and B, if A is in P, then A is reducible to B?

For any two problems A and B, if A is in P(complexity) then A is reducible to B. Could anyone explain why this is true?

Solving SAT by converting to disjunctive normal form

The first well-known $NPC$ problem is the Boolean Satisfiability Problem, which has a proof of being $NPC$ done by Cook (Cook-Levin Theorem). The problem can easily be described the following way: In complexity theory, the satisfiability problem (SAT) is a decision problem, whose instance is a Boolean expression written using only AND, OR, NOT, variables, […]

What are NP-complete problems and why are they so important?

I keep hearing questions about whether something is NP-complete, but they never really mention what it is. Why do people care so much about NP-complete problems?