Questions tagged [np-complete]

Questions about the hardest problems in NP, i.e. of those that can be solved in polynomial time by nondeterministic Turing machines.

1,412 questions
Filter by
Sorted by
Tagged with
25 views

Polynomial reduction to SAT with a condition

Let L be in NP. Is there always a reduction from L to SAT where atleast m-1 clauses (m being the number of clauses in the CNF formula) can be satisfied? When w is in L it is trivial because the ...
20 views

Proof that there isn't a $c$-additive approximation to Partition Problem

Define Partition to consist of all tuples $x_1,\ldots,x_n$ which can be divided to two groups in which the sums of the two groups are equal. Is there a proof that there isn't an additive approximation ...
25 views

Minimum number of intervals to cover all possible colors

Given $n$ points in $\mathbb{R}$ each colored with one of following three colors $$C=\{c_1, c_2, c_3\}.$$ In polynomial time, Choose the minimum number of intervals of length $1$ each containing some ...
29 views

Difficulty in finding a counter example for a polynomial reduction

I am doing some exercises on proving NP Complete problems and the first problem was directed bipartite graphs with a Hamiltonian cycle and the second one was undirected bipartite graphs with a ...
24 views

How to reduce 3-SAT to Set Splitting

I've been reading through Garey & Johnson's "Computers and intractability", and a problem SP4 caught my attention. It is stated as following: Given a collection $C$ of subsets of a ...
20 views

194 views

How to reduce SUBSET-SUM with integers to SUBSET-SUM with non-negative integers?

The subset sum problem is as follows: Given a sequence of integers $\mathcal S=(a_1, ..., a_n)$ with cardinality $n$ and an integer $T$, determine whether there is a subsequence of $\mathcal S$ whose ...
119 views

Prove TILING is NP-Complete

I have a homework task to show that $\mathrm{TILING} = \{(T, 1^N) \mid \text{it is possible to cover } N \times N \text{ square with tiles from }T\}$, where $t\in T$ is $C^4$ for some color set $C$, ...
48 views

How do I prove that the clique problem is polynomial-time reducible to the odd cycle transversal problem?

I have the following problem: Let $H=(W, F)$ a graph and $k \in \mathbb{N^*}$ be an instance for problem $\textbf{CMP}$ (i.e. the clique problem). Let $W'$ a set of new vertices, $|W'|=|H|=n$. We ...
37 views

Is Self-Modifying Turing Machine equivalent to NTM or TM?

Let SMTM be Turing Machine, but the commands recorded in which can change to others in some random way (for example, choose with a 50/50 probability the command to move to the right or move to the ...
26 views

Probably this is a basic question but I'm not sure how to finish this proof. I have a problem $X$ and I want to prove that it is possible to reduce $X$ to another problem $Y$. I know that $Y$ is NP-...
36 views

35 views

Does reducing a NP Hard problem to a NP problem make that NP hard problem a NP Complete problem?

I was asked a question in my algorithms exam which had this as the core question after simplifying. I had written that it would be NP-Hard but I got it wrong my professor is saying that it would be NP-...
70 views

Find the class of the problem PP1 and PP2 using the information given below

Assume that P1, P2,..., Pn are all NP-class problems. PP1 and PP2 are unknown problems (i.e., we don't know whether they belong to the P or NP classes). If "P1, P2,...., Pn" problems can be ...
40 views

182 views

NP-completeness of satisfiability of formula over 50 variables

Given a boolean formula $F$ of length $n$ defined over a fixed number of variables (say 50), is it NP-complete to decide whether $F$ is satisfiable?
37 views

Can one show NP-completeness by showing a reduction to 3SAT?

The standard technique to show NP-completeness of $L$ seems to be to show that $L$ is in NP, and then to show that some NP-complete language can be reduced to it. What if one tried to show it the ...
201 views

Is there an instance of 3-SAT in less than 100 variables that no one has been able to solve?

In number theory, progress is sometimes guided by people stating a specific Diophantine equation that they don't know how to solve. Is there anything similar in the field of Boolean satisfiability? ...
17 views

Complexity class of computation of Homfly polynomial

It is claimed that "the problem of the computation of the homfly polynomial is NP-hard." but is it known if it is NP-complete? By the definition of NP-completeness, wouldn't it be enough to ...
Approach:1 To prove any unknown problem $B$ is NPH then take any known NPH problem $A$ (e.g. $3$-sat) which reduces to $R$ in polynomial time. If I take any instance example $I_1$ of $A$, then ...
If $A\leq_m^\mathsf{}B$ and $B$ is a regular language, does that imply that $A$ is a regular language?
Corollary:1 We know that if $A\leq_m^\mathsf{}B$ and $B$ is decidable then $A$ is also decidable. This is because if there exists a specific algorithm for solving $B$ and we can also reduce $A$ to $B$ ...