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
0
votes
0answers
12 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
52 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
40 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
35 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
124 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
55 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.
2
votes
0answers
24 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, . . .,\...
0
votes
0answers
39 views

A variant of the knapsack problem

Consider the following variant for the knapsack problem: the input are disjoint sets of items $ T_1, T_2, ..., T_m$ (each contains items of a different type). Every item $i$ has a value of $v_i$ and a ...
0
votes
1answer
28 views

how to proof ${ NPC \bigcap CO-NPC \ne \varnothing then NP = P ? }$

how proof ${\ \ NPC \ \ \bigcap \ \ CO-NPC \ne \varnothing }$ then ${NP = P ? }$
1
vote
0answers
24 views

Looking for some references on voting theory

After reading through this paper on optimizing the sum of sigmoid functions, http://www.web.stanford.edu/~boyd/papers/pdf/max_sum_sigmoids.pdf, I am interested in the problem addressed in section 7.3 ...
1
vote
0answers
12 views

What is the FPTAS algorithm to find flow at each link for multi commodity flow problem?

I have a graph and K commodities to route from source to destination. I want to find, what is the maximum beneficial flow for each of the commodity and the relevant paths. I understand the problem in ...
4
votes
0answers
24 views

Strongly connected subgraph that contains no negative cycles

Is there an efficient algorithm that solves the following decision problem: Given a strongly connected weighted directed graph $G$, defined by its transition matrix, is there a strongly connected ...
0
votes
1answer
20 views

Clarifying what it means to be Strongly NP-Complete

Wikipedia defines strongly NP-Complete as: A problem is said to be strongly NP-complete, if it remains so even when all of its numerical parameters are bounded by a polynomial in the length of the ...
2
votes
0answers
29 views

Disjoint paths in digraphs is NP-complete

In the article: S. Fortune, J. Hopcroft, J. Wyllie, The directed subgraphs homeomorphism problem, Theoret. Comput. Sci. 10 (1980) 111–121. link: https://www.sciencedirect.com/science/article/pii/...
0
votes
0answers
31 views

How to know if a problem belongs to NP Class?

What I know (NOT strictly speaking): I know that there is an open question about the equality of P and NP Classes and as long as there is no known algorithm that solves NP problems in P time then we ...
3
votes
1answer
125 views

maximum coverage version of dominating set

The dominating set problem is : Given an $n$ vertex graph $G=(V,E)$, find a set $S(\subseteq V)$ such that $|N[S]|$ is exactly $n$, where $$N[S] := \{x~ | \text{ either $x$ or a neighbor of $x$ ...
2
votes
1answer
64 views

Is SAT a single language or a union of languages?

I know that a language is in NP if a Turing machine can decide the language of its checking relation $\{\text{boolean formula }\#\text{ truth assignment | truth assignment is correct}\}$ in polynomial ...
3
votes
2answers
87 views

Coloring an interval graph with weights

I have an interval graph $G=(V,E)$ and a set of colors $C=\{c_1,c_2,...,c_m\}$, when a color $c_i$ is assigned to a vertex $v_j$, we have a score $u_{ij}\geq 0$. The objective is to find a coloring of ...
9
votes
2answers
175 views

Prove that the 2-approximation of a modified local search algorithm for max-cut is tight

Consider the following local search approximation algorithm for the unweighted max cut problem: start with an arbitrary partition of the vertices of the given graph $G = (V,E) $, and as long as you ...
4
votes
1answer
48 views

Partition into paths in a Directed Acyclic Graphs

I have a directed acyclic graph $G=(V,A)$, I want to cover the vertices of $G$ with a minimum number of paths such that each vertex $v_i$ is covered by $b_i$ different paths. When $b_i=1$ for all the ...
3
votes
3answers
162 views

You prove that vertex cover reduces to some problem A, does that mean that A is NP-Complete?

My question is essentially the title. Let's say you have some random problem A. You prove that Vertex Cover (which is NP-Complete) reduces to A. You know nothing else about A besides that Vertex Cover ...
0
votes
0answers
14 views

Which instances of Exact Cover are considered hard?

In the Exact Cover formulation there are $N$ variables and $M$ "clauses''. For the special case when each clause contains exactly $3$ variables it is called 3-Exact Cover. Now, I've read in articles ...
0
votes
1answer
65 views

Show that a problem is NP-Complete

The problem is, K_longestPath: We are given a graph in which some of the vertices are "cities". No two cities have an edge between them, thus every city must be at distance at least 2 from each ...
0
votes
1answer
73 views

P Vs NP can never be proven one way or the other!

Okay, so I was reading a bit about P vs NP problems. And I found out that proving P Vs NP is an NP problem. And since if we prove that any problem in NP is a P that would mean that we have NP=P. ...
1
vote
1answer
41 views

Encoding order relations in CNF

I want convert timetable scheduling problems to SAT problems. Suppose there are $t$ time slots and $c$ classes. I will define $t\times c$ variables $x_{ij}$, which is true iff class $j$ takes place in ...
0
votes
1answer
70 views

triangle inequality TSP is NP-complete?

I have been reading online source and it mentioned triangle inequality TSP is NP-complete but without proof. In general, the reduction from HAM-cycle problem to TSP works for asymmetric and symmetric ...
0
votes
0answers
58 views

If any problem in NP is not in P then NP C ∩ P = ∅

If any problem in NP is not in P then NPC ∩ P = ∅ The proof is: We have $X ∈ NP$ and $X \not\in P$. Assume $Y ∈ NP C ∩ P$. As $X ≤_P Y$ we have $X ∈ P$, which is a contradiction. I have not clear ...
3
votes
1answer
47 views

Partitioning bag of sets such that each set in a group has a unique element

Suppose I have a bag (or multiset) of sets $S = \{s_1, s_2, \dots, s_n\}$ and $\emptyset\notin S$. I wish to partition $S$ into groups of sets such that within each group each set has at least one ...
0
votes
1answer
75 views

NP-completeness for integer linear program

This is a homework problem, so I don't want the solution. I need a hint which problem to reduce to the following and/or how to start on it. We were thinking of TSP or independent set but couldn't come ...
1
vote
1answer
48 views

Independent set problem

I'm referring to a post here,https://www.transtutors.com/questions/suppose-that-someone-gives-you-a-black-box-algorithm-a-that-takes-an-undirected-grap-1706946.htm# Question: Suppose that someone ...
1
vote
2answers
54 views

Prove the Droid Trader Problem is NP-complete

This question is from chapter 8, exercise 35, of Algorithm Design by Kleinberg and Tardos. A player in the game controls a spaceship and is trying to make money buying and selling droids on ...
1
vote
1answer
36 views

Algorithm for idempotent algebra

A boolean algebra expression can be converted into an idempotent algebra using $$\bar a \equiv 1-a, \qquad a \vee b \equiv a+b -ab, \qquad a \wedge b \equiv a \otimes b$$ where $\otimes$ is the ...
2
votes
2answers
223 views

How to prove LastToken problem is NP-complete

Consider the following game played on a graph $G$ where each node can hold an arbitrary number of tokens. A move consists of removing two tokens from one node (that has at least two tokens) and adding ...
-1
votes
1answer
33 views

Another Subset sum problem

Verify that (S = {83, 88, 93, 67, 57, 89, 78, 51, 95, 98, 69, 49}, t = 492) is a positive instance of Susbset Sum.
1
vote
0answers
20 views

Show that SQUARED-SUM-PARTITION is NP-complete

Consider the following problem SQUARED-SUM-PARTITION. You are given positive integers $x_1, \dots, x_n$, and numbers $k$ and $B$. You want to know whether it is possible to partition the numbers $\{ ...
1
vote
1answer
53 views

Subset sum to 0/1 knapsack

How can I translate (i.e. reduce) an arbitrary instance $(S, t)$ of Subset Sum into an instance of 0-1 Knapsack? I'm also given a hint: you may assume that all members of $S$ are positive integers.
0
votes
1answer
34 views

Can someone pelase give a counter example of it? If a problem is in NP then there is no known polynomial time algorithm to solve it

Is there any known polynomial time algorithm to solve a problem which that problem is in NP. I was told is False but can't think of any counter example now.
1
vote
1answer
32 views

NP Complete Clique Variation

I have the following problem I am trying to prove NP Complete. Tutors have two jobs- grading exams and homework help. Suppose we have a set of $n$ tutors. Each of them can tutor any amount of $m$ ...
2
votes
1answer
45 views

Finding a vertex coverage that is also an independent set

Given a graph $G$ and integer $k$, find a vertex coverage set of size $k$ that is also an independent set. I need to either prove this problem is np-complete or find a polynomial solution. Any idea?
1
vote
1answer
22 views

How to prove that Exact Cover is NP-complete using SAT?

I found this solution online here, but I do not understand the logic behind transforming the instance of SAT to an instance of Exact Cover. Here's the solution from the link (where C is the clause(...
5
votes
1answer
142 views

Using decision oracle to solve optimization problem of maximum polyomino tiling

So, this problem is a kind of variant of polyomino packing which has been discussed frequently elsewhere, but I haven't been able to find anything on my particular problem. Suppose we have a list of ...
2
votes
1answer
70 views

If A and B are NP-complete, then A ∪ B need not be NP-complete

I am studying the proof of this exercise (link) There exist N P-complete languages A and B such that A ∪ B is not N P-complete. Example: $A = \{1x : x ∈ SAT\} ∪ \{0x : x ∈ \{0, 1\}^∗\};$ $B =...
0
votes
0answers
63 views

Using induction prove that a K-SAT problem is NP-Complete

Using induction on k, how do I prove that the K-SAT problem is NP-complete? On wikipedia, it describes the Cook-Levin theorem to prove that K-SAT is NPC by reducting the K-SAT problem to a circuit-...
1
vote
1answer
46 views

Finishing degree requirements NP-complete: Choosing 1 element from each set avoiding conflicts

The question, which I have slightly paraphrased to get rid of the fat, is this: There are $k$ areas of study in which you need to take 1 course. For each area of study, there is a set of courses $C_1,...
3
votes
1answer
22 views

CNF satisfiability with a bound on number of clauses

Consider the CNF-sat problem with n literals and k clauses. If k scales linearly in n, we get np-completeness (e.g., 3-sat where each literal appears at most 4 times). Do we still get np-completeness ...
1
vote
1answer
34 views

Are all subsets of NP-complete languages also NP-complete?

Is the following assertion true or false? If the language $L$ is NP-complete and $Q ⊆ L$, then $Q$ is NP-complete. I know for example that $k$-coloring is NP-complete if I take $k$ as input, but 2-...
0
votes
1answer
139 views

How to prove Exact cover problem is NP Complete using Vertex Cover problem?

Using reduction theorem in NP, we want to prove that Exact cover is NPC by reducing it from Vertex Cover Problem. It is easy to derive it from SAT, but we can't find a solution yet to derive it from ...
0
votes
1answer
27 views

Would an optimization version of the 3-partition problem also be strongly np-complete / np-hard?

Anyone know if an optimization variant of the 3-partition problem (as explained there) would also be strongly np-complete? This would be where the goal is to group a multiset whose size is evenly ...
4
votes
2answers
57 views

Given a set, partition it into ordered triples

I have a set $S$ of $3m$ positive numbers $\{a_1,a_2,\ldots,a_{3m}\}$. The question is: can you select $m$ disjoint triples $(a_i,a_j,a_k)$ from $S$ such that $a_i-a_j-a_k\geq1$? I was trying to ...