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.

Filter by
Sorted by
Tagged with
3
votes
1answer
57 views

Dynamic Program to solve an NP-complete partitioning problem

I have this problem for which I am struggling to find an efficient dynamic programming algorithm. Would be thankful for some help!! Let $A = \{ a_1, a_2, ..., a_n \}$ be a set where $a_i \in \mathbb{...
2
votes
1answer
24 views

Vertex cover problem modification such that every vertex is connected to the set, NP-Hard?

Being new to complexity problems, I've met a question that is quite similar to the Vertex Cover Problem and I am not sure if this one is NP-Hard. We know that the vertex cover problem is the following:...
1
vote
1answer
27 views

Does this problem map to the Set Packing problem?

Let $G(m,n)$ be A bipartite graph $G$ with paritions $m$ and $n$ with the property that partition $\mathit n$ has two types of nodes (type1 or type2). Given $G(m,n)$ and $k \in \mathbb Z+$: Does $\...
1
vote
2answers
61 views

Proving NP-completeness of a surveilled graph problem

So suppose I have a graph consisting of a tuple $(V,E,A,g)$ where $V$ denotes vertices, $E$ denotes edges, $A$ denotes a subset of $V$ (i.e. $A \subseteq V$), and $g:A\rightarrow\mathbb{N}$ is a ...
0
votes
1answer
25 views

A non-polynomial reduction

Given two problems $P_1$ and $P_2$. $P_1$ is NP-complete in the strong sense and we want to prove that $P_2$ is also NP-complete but the reduction from $P_1$ to $P_2$ is not polynomial. Can we say ...
-4
votes
0answers
29 views

Proving NP completness

Let G = (V, E) be a directed graph. Consider the problem of dividing V into two disjoint parts A and B such that there does not exist directed cycles in A or B. Prove that this problem is NP-complete. ...
0
votes
0answers
35 views

Isn't every polynomial time problem an NP problem?

See here. Knapsack problem -- NP-complete despite dynamic programming solution? The only reason Knapsack problem is NP-complete is because input comes as binary numbers so n is actually 2^n. Since ...
1
vote
1answer
44 views

Prove a TM problem is NP-complete

Question: Show that $T_{NP}$ is NP-complete, where $$T_{NP} = \{m\#w\#^c\mid M_m\text{ is an NTM};M_m(w)\text{ has an accepting computation of $\leq$ c steps}\}$$ This question looks weird to me ...
0
votes
1answer
24 views

If there is an polynomial time approximation to an NP-complete problem, is P approximately NP?

Deciding bipartite hypergraph coloring is NP-hard: While for bipartite graphs a 2-coloring can be found in linear time, it was shown by Lovasz [10] that the problem to decide whether a given k-...
10
votes
1answer
2k views
+50

What is wrong with this simple proof of P=NP?

Exactly 1 in 3 SAT ($X3SAT$) is a variation of the Boolean Satisfiabilty problem. Given an instance of clauses where each clause has three literals, is there a set of literals such that each clause ...
4
votes
1answer
74 views

Query: Given a graph, is edge x in an optimal TSP tour?

Consider the decision problem that when given a graph, we need to decide if a particular edge belongs to any optimal solution to the traveling salesman problem on that graph. It may be argued that ...
3
votes
2answers
39 views

Finding a hamiltonianISH path in a graph

Problem statement Given a graph of all the blue squares in the following image where each blue square is connected to other blue squares in all 4 cardinal directions. Given any starting node. What ...
2
votes
1answer
38 views

How to prove the NP-completeness of MOD-PARTITION

MOD-PARTITION: Given a set of integers $A={a_1,...,a_n}$, their weights $w = \{w_1, w_2, \dots, w_n\}$ and the number $k$, does there exist a subset $X$ of $A$ such that: $(\sum_{x \in X} w(x) * x) \...
0
votes
0answers
31 views

how to prove this problem is NP complete? [closed]

Given a graph G = (V, E) and two integers a, b, does there exist V' ⊆ V such that |V'| = a and |(V' × V') ∩ E| ≥ b. That is, the problem is to determine if there is a subset of vertices of size at ...
1
vote
0answers
88 views

Prove Product Partition is NP-complete in the strong sense

I am trying to understand how to prove that the Product Partition problem is NP-complete in the strong sense. The problem is similar to the normal Partition problem, except in this case the product of ...
0
votes
1answer
86 views

When is a problem strongly NP-complete

Let the problem of the diophantic equation 0/1 be as follows. Input : A polynomial equation on n variables whose coefficients are integers (ex : $2x^3_1 x_2 + x_1x^3_3 - 3x_4 = 8$) Question: Does ...
0
votes
1answer
26 views

Does the language defined in the details in NP-C or P?

It's known that: $$ \textrm{CLIQUE} = \{(G,k): \mbox{G has a clique of size } k\} $$ is $\textrm{NP-C}$, but what if every vertex has 2 neighbours (as defined in $\textrm{2d-CLIQUE}$)? $$ \textrm{2d-...
1
vote
3answers
49 views

NP-complete problem 3-SAT, is there a difference in complexity between just providing yes/no without exact solution

The 3-SAT problem is NP-complete, meaning that no known algorithm can provide an exact solution in polynomial time, while a solution can be tested very quickly in polynomial time. My question is, ...
-1
votes
0answers
20 views

How to prove that degree-4-IS si NP-Complete

I would like to have an idea to solve this kind of problem. Let us call degree-k-IS the restriction of the problem of the independent set to graphs of degree maximum $k$. Show that the degree-4-IS ...
0
votes
1answer
81 views

Restriction of SAT to CNF

I have spent a lot of time understanding these two issues. If you can help me, please. Prove that the restriction of SAT to CNF formulas in which each variable xi appears at most twice is solvable in ...
1
vote
1answer
76 views

Prove Lecture Planning is NP-complete

This is a practice problem from my algorithms class. (And no, it was not assigned as homework. I can't prove this, but you don't have to answer if you don't believe me.) To me this seems like a very ...
0
votes
0answers
29 views

K-Uniform Hypergraph Strong Coloring

I want to ask if strong coloring of a k-uniform hypergraph using only k colors is NP-Hard or NP-Complete? If you can add a reference this will be helpful.
1
vote
5answers
144 views

NP-hard or not: partition with irrational input or parameter

See some related questions in Cont: NP-hard or not: partition with irrational input or parameter Given a set $N=\{a_1,...,a_{n}\}$ with $n$ positive numbers and $\sum_i a_i=1$, find a subset $S\...
2
votes
0answers
87 views

PTAS for Multiple Knapsack with Uniform Capacities, fixed number of Knapsacks

Consider the following problem: We are given a collection of $n$ items $I = \{1,...n\}$, each item has a size $0 < s_i \le 1 $ and a profit $ p_i > 0 $. There are $m$ (a fixed number) of unit-...
0
votes
0answers
28 views

Scheduling jobs on a single machine - minimising the weighted sum of completion times

Consider the following problem: there are $n$ jobs $\{1,...,n\}$, each has a processing time, $p_i$, a weight $w_i$, and an arriving time $r_i$. The goal is to minimise the weighted sum of completion ...
4
votes
1answer
68 views

Two versions of Subset Sum Problem

I keep seeing two versions of the Subset Sum Problem. The first and seemingly least common is: Given an integer bound $W$ and a collection of $n$ items, each with a positive integer weight $w_i$, ...
0
votes
1answer
28 views

Minimum total waiting time for arrivals/durations

I have come up with the following problem, and cannot seem to find an effective way of solving it: Consider $n$ clients arriving at a service point at time moments $\{a_i\}_{i=1}^n$ whose duration ...
0
votes
0answers
10 views

Are all NP-complete languages downward self-reducible?

Arora-Barak says that using the Cook-Levin reduction, one can show that all NP-complete problems are downward self-reducible. I know that SAT is downward self-reducible but I am not able to see how we ...
1
vote
0answers
29 views

Obtaining a graph with no cycles after removing k edges

I am looking for an algorithm that upon an input of a directed graph G and a natural number k,outputs a set of k edges, that upon removing them, the graph will have no cycles. If there are no such k ...
0
votes
1answer
43 views

Obtaining an acyclic graph by removing edges using an algorithm that decides ACYCLIC

i don't understand the following: If there's an algorithm that can decide ACYCLIC in Polynomial time, then there's an algorithm who returns a set of k edges, so that the graph obtained by deleting ...
24
votes
5answers
7k views

P = NP clarification

Let's use Traveling Salesman as the example, unless you think there's a simpler, more understable example. My understanding of P=NP question is that, given the optimal solution of a difficult problem,...
1
vote
1answer
33 views

polynomial reduction & co np complete

I would like to know how we can demonstrate these two problems : $A \leqslant_p B$ implies $\overline A \leqslant_p \overline B$ The complement of 3-SAT is co-NP-complete
2
votes
1answer
49 views

Special Monotone SAT problem: NP complete?

Say we have the set $X=\{ x_1, x_2, \dots \}$ of variables. Then we consider the following problem: Is the formula $$\bigwedge_{(a,b,c) \in A}(a \vee b \vee c) \wedge \bigwedge_{(a,b,c) \in B}(\neg a ...
1
vote
0answers
58 views

NP-completeness of crossword puzzle

How to prove that this crossword puzzle is NP-complete? We have an instance of crosswords in a square grid $G$ ​​of size $m \times m$. We have a set of black boxes $N$. We have a dictionary of words ...
6
votes
1answer
94 views

Select at least one from each category to minimize union, NP-hard problem?

I have this problem that is very similar to the minimum k-union problem: Given a collection $C$ of subsets of a finite set $S$ and each set $c\in C$ has a label that is its category. The problem is ...
0
votes
0answers
12 views

Is DHAMPATH downward self-reducible?

DHAMPATH is the set of all the directed graphs which have a hamiltonian path. It's a well known NP-complete problem. I know the proof of SAT's downward self-reducibility. Arora-Barak says Cook-Levin'...
5
votes
0answers
41 views

Why the Cook-Levin reduction is not a parsimonious reduction?

In the textbook Arora-Barak, after presenting the Cook-Levin theorem's proof the authors say that the proof can be modified slightly to make the reduction parsimonious. The parsimonious reduction is ...
3
votes
1answer
113 views

Polynomial-time linear-reduction from Directed Hamiltonian Path Problem to 3SAT

Is there a polynomial-time reduction from Directed Hamiltonian Path Problem to 3SAT which is linear in the number of vertices? That is, it reduces every directed graph $G$ with $n$ vertices to a ...
1
vote
2answers
50 views

Is the number of NP-complete problems finite?

It should be straight forward to show that there are infinitely many NP-hard problems: Proof: Take the problem Remove 1 Vertex 3-COL ($R1V3COL$) which takes a graph $G=(V,E)$ as an instance and ...
2
votes
1answer
55 views

NP-completeness of a problem with pretty fast algorithm

Supposing if a problem with $n$ non-deterministic bits is in $O(2^{\alpha n})$ time at every $\alpha\in(0,1)$ then is there evidence that problem can or cannot be $\mathsf{NP}$-complete?
2
votes
0answers
22 views

A polynomial time reduction and the size of problem (exact cover)

An exact cover problem is one of the NP-complete problems. Given a family $\mathbb{I}$ of subsets of a set $[n]=\{1,\dotsc,n\}$, whether there exists a subfamily $\mathbb{I}'\subseteq \mathbb{I}$ ...
1
vote
0answers
17 views

Is exact cover with sumsets NP-Complete

Given a group $G$, the sumset of two sets $A,B$ is denoted as $A+B = \{a+b:a\in A,b\in B\}$. We have that $A+B$ has no multiplicities if $|A+B| = |A||B|$. For practically, let's say $G$ is integer ...
0
votes
1answer
26 views

NP-Complete reductionTrue/False question explanation

Why is the above statement true? my understanding is: (1)3SAT reduces to X implies X is NP-complete or harder. (2)Set Cover reduces to X implies X is neither NP-Complete nor harder. This ...
1
vote
1answer
67 views

An NP-hard problem reduces to its complement?

I found this statement in a true/false test section: Could someone explain in laymans why this is a true statement? My understanding is that if $X$ is $\mathcal{NP}$-hard, then its complement must ...
2
votes
1answer
55 views

Is the Clique Problem polynomial time reducible to the graph-Homomorphism Problem and if so what does the reduction look like?

Is the k-Clique Problem (given a Graph G and a natural number k does G kontain a Clique of size k) polynomial time reduzible to the graph-Homomorphism Problem (given two graphs, G and H, is there a ...
0
votes
1answer
43 views

In which paper is written that you can transform one problem to another to show NP-completeness?

For example in this post they discuss how to construct a reduction between problems to show that one probleme is NP-Hard: Post I am searching for a scientific paper to cite where it is written, that ...
0
votes
2answers
150 views

What is wrong with the following $P$ problem?

Our teacher gave us the following statement and we were wondering what is wrong with it. Consider an array $A$ of $n$ distinct numbers. Since there are $n!$ permutations of $A$, we cannot check ...
2
votes
1answer
63 views

Are problems in NP $\cap$ coNP less difficult than those in NP-complete?

I am taking a complexity class now, and I struggle to understand the concept of "hardness": Assume that $L \in \textsf{NP } \cap \textsf{coNP}$. In means that under the assumption $\mathsf{NP} \neq \...
1
vote
1answer
2k views

A problem in NP but not NP-complete?

Graph isomorphisim is not proven to be NP-complete what would it imply if it were possible to prove that there are some problems which are in NP set of problems but not in NP-complete set.
4
votes
1answer
34 views

On the hardness of constraint satisfaction

I am interested in the hardness of the following question. Suppose we have a vector of $n$ optimization variables $\mathbf{x} = \langle x_1, . . ., x_n\rangle $ and $m$ vectors $\mathbf{v}_1, . . .,\...

1
2 3 4 5
23