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

learn more… | top users | synonyms

-1
votes
1answer
37 views

Restricted version fo CNF-SAT

Given formula $\phi$ on CNF-form in CNF-SAT. Clauses can be arbitrarily long. The problem is NP-complete and it is also given that part of the problem is that a variable can occur many times in a ...
0
votes
1answer
47 views

NP-Completeness - Reducing CLIQUE

Given a graph $G$, and integers $c$ and $k$, a group $X$ is a set of nodes $v_1, v_2, \dots, v_{|X|}$ that each have degree at least $c$ and that form a complete subgraph of $G$. Following decision ...
3
votes
1answer
46 views

Discrete solution space in NP-complete problems

While there are many known NP-complete problems, they all seem to be discrete in the solution space. What is the underlying principle for this?
-2
votes
1answer
41 views

If an NP problem reduces to an NPC problem, it is NPC?

Is the following statement true? If a problem P1 is in NP and polynomial time reducible to P2, where P2 is NP-complete, then P1 is also NP-complete. Intuitively I think the answer is No because ...
14
votes
3answers
135 views

Is there a complexity viewpoint of Galois' theorem?

Galois's theorem effectively says that one cannot express the roots of a polynomial of degree >= 5 using rational functions of coefficients and radicals - can't this be read to be saying that given a ...
2
votes
1answer
37 views

Reduction from 3 SAT to Monotone Exact 1 in 3 SAT

Can someone please help with a clear reduction from a 3SAT to a Monotone Exact 1 in 3 SAT. I tried searching by didn't find much.
3
votes
1answer
56 views

What do we know about $NP \cap co-NP$?

What do we need about the intersection of $NP$ and $co-NP$ apart from the fact that $P$ is a subset of it? (beyond what these answers here say, What do we know about NP ∩ co-NP and its relation to ...
3
votes
1answer
157 views

Are all NP-complete languages log-space reducible to each other?

NP-complete languages are reducible to each other in polynomial time. Does this mean that they are also log-space reducible to each other? It seems as if this is true because in log-space, we can ...
-3
votes
0answers
47 views

Is this problem NP complete?

Given $\{a_i\}_{i=1}^n\in\Bbb N^n$, is there a $v\in\Bbb N^n$ such that $$\prod_{i=1}^na_i^{v_i}\in[L,U]$$ where $(L,U)\in\Bbb N^2$? Each of $a_i,v_i,L,U$ has $O(n^c)$ bits with some fixed ...
2
votes
1answer
70 views

Reduce our problem to a known np-complete problem

Subgraph isomorphism We have the graphs $G_1=(V_1,E_1), G_2=(V_2,E_2)$. Question: Is the graph G_1 isomorphic with a subgraph of $G_2$ ? (i.e. is there a subset of vertices of $G_2, V \subseteq ...
-1
votes
2answers
52 views

Time Complexity of k-clique problem with fixed k [closed]

My question expands on a related question on the link, Why is the clique problem NP-complete? In that post the author argued that while the $k$-clique problem is NP-complete; for a fixed $k$ the ...
0
votes
1answer
46 views

Is Weighted Vertex Cover NP-Complete? [duplicate]

I'm doing practice problems for an upcoming exam and I'm unsure if the following problem is NP-complete. If it is can you please give me a hint as to what problem I should reduce to it. I believe it's ...
1
vote
1answer
35 views

np-complete proof, turing reduction

I have some difficulties with a complexity proof : I work with 3 problems : A, B and C I know : A-> B A-> C C -> B A-> B meaning : if I have a "yes answer " for A , then I have a "yes answer" for ...
1
vote
1answer
52 views

NP HARD Problem Longest Path in Graph

I got stuck with this problem since the whole day. When we are finding the longest path in a graph we first do topological sorting and then check the path of adjacent vertices and keep upgrading ...
5
votes
1answer
104 views

Reduction from Vertex Cover to Polygon Cover

Polygon Cover: Input: A set of points $P$, a set of polygons $S$ in a 2D plane, and a positive integer $k \in \mathbb{N}$. Output: True if and only if there exists a subset in $S$ of at most $k$ ...
2
votes
0answers
26 views

Proof sketch that NP total search problems cannot be NP-complete [duplicate]

From a blog post, about proving that NP total search problems cannot be NP-complete unless NP=co-NP. It's possible to write a convincing proof sketch as follows. Consider what would it would mean ...
1
vote
1answer
68 views

What can I deduce if an NP-complete problem is reducible to its complement?

Let's say I have a decision problem $D$ and its complement $D'$. I know D is poly-time reducible to $D'$ (its complement). Furthermore, I know $D$ is NP-complete. What is the strongest statement I ...
2
votes
1answer
66 views

Relationship between Independent Set and Vertex Cover

Directly from Wikipedia, a set of vertices $X \subseteq V(G)$ of a graph $G$ is independent if and only if its complement $V(G) \setminus X$ is a vertex cover. Does this imply that the complement of ...
0
votes
1answer
48 views

Poly-time reduction: D and D Comp [duplicate]

Looking at the Independent Set problem and its complement, I want to show that IS is poly-time reducible to its complement, however I am struggling on coming up with the reduction function. I will ...
3
votes
1answer
68 views

Optimization in multivalued logic. Optimal strings with given patterns

This question comes from an application in multivalued logic. Suppose, we are given an alphabet of three letters $A, B, C$ and a set of indices $1,2,3,4,5$. Consider items formed by subscripting the ...
1
vote
0answers
52 views

Lower bounding the minimum equivalent graph

The transitive reduction $G^t = (V,E^t)$ of a graph $G=(V,E)$ is the smallest graph with the same reachability as $G$ with the property $E^t \subseteq V \times V$. The minimum equivalent graph $G' = ...
0
votes
0answers
72 views

Is the weighted transitive reduction problem NP-hard?

The transitive reduction problem is to find the graph with the smallest number of edges such that $G^t = (V,E^t)$ has the same reachability as $G=(V,E)$. When $E^t \subseteq E$ it is NP-complete. ...
2
votes
3answers
73 views

Could an NP-Hard problem be in P in after a basis transform? [closed]

I'm aware that there must be something wrong with my reasoning, but I'm not sure what and neither are a few other CS people I've asked. So here goes: Take the following problem for example: Let ...
-1
votes
2answers
188 views

Some inference about NP

this is my first question on this site. I‌ recently, study on NP. I have some confusion about this Topic, and want to propose my inference and some one verify me. I) each NP problem can be ...
3
votes
3answers
307 views

The relation between 2SAT and 3SAT

Show that proving 2SAT is not NP-Complete would prove that 3SAT is not in P. Or eqivalently - Show that proving 3SAT is in P would prove that 2SAT is NP-Complete. I can see there is an ...
1
vote
0answers
64 views

Totally unimodular <=> polynomial time?

Crossposting due to recommendation. I formulated a MIP problem which I didn't expect to be unimodular. The problem is to find a minimum complete sequence in a strongly connected digraph. That is, ...
0
votes
1answer
62 views

Array search NP completeness

Given an unsorted array of size n, it's obvious that finding whether an element exists in the array takes O(n) time. If we let h = log n then it takes O(2^h) time. Notice that if the array is ...
-2
votes
1answer
30 views

NP != P Proof Requirments [duplicate]

I have been examining the NP = P problem and I am wondering, why is proving or disproving NP = P hard? For example, why wouldn't a proof such as the following be adequate? Suppose a million doors were ...
3
votes
2answers
59 views

Restricted Integer Programming

The integer feasibility problem is NP-complete: $Ax=b, x \geq 0, x \mbox{ integer}$ $A$ contains elements in $\mathbb{R}$ If we restrict this: $A$ contains only elements in: $\{1,0\}$ ...
1
vote
1answer
18 views

How is the complexity of algorithms to solve 3CNF (decision problem) specified? [duplicate]

For k inputs, the complexity of naive algorithm is O(2^k). I understood this one. What is meant by "the size of the instance to be solved should be polynomial in k". Is it equivalent to the statement ...
3
votes
1answer
29 views

Pseudo polynominal time algorithm for Np-Complete Problems

For problems like knapsack there is pseudopolynominaltime algorithm and it is np-complete. So we reduce every other problem in np in polytime to knapsack. But why don't we have then a ...
0
votes
0answers
14 views

Subexponential algorithm for Np-complete problems [duplicate]

http://cstheory.stackexchange.com/a/3627/32204 Could someone explain to me why this reasoning is false. I don't understand it! To me this sounds plausible!
2
votes
1answer
16 views

Is it Polynomial to decide whether any product of input numbers satisfies a boolean expression?

I have an input number c of n bits and its prime factorization. I want to find a divisor of c with certain fixed bits "f". For example: ...
0
votes
1answer
36 views

Not Hamiltonian is in NP Class? [duplicate]

I ask a question before, Questions on Graph and Hamiltonian, but i ask it here with different challenging contest. From this book and other study in complexity theory, I have seen the following ...
0
votes
1answer
51 views

Satisfying assignments, twice-3SAT NP complete [duplicate]

I wanted to solve the following problem about 3SAT . The question is 1. to show if the problem is NP-complete and 2. whether the problem has two different satisfying assignments. "TWICE-3SAT Input: ...
2
votes
1answer
82 views

Questions on Graph and Hamiltonian [closed]

From this book and other study in complexity theory, I have seen the following statement: The definition of NP is not symmetric with respect to yes-instances and no-instances. For example, it is ...
3
votes
3answers
155 views

4-color to 3-color polynomial reduction

I know a simple reduction from 3-color to 4-color. But how do you reduce 4-color to 3-color ? I have been searching for the right way to make this reduction for a while now. I would love some ...
2
votes
1answer
44 views

What is the implication of NP-completeness if P=NP?

If a certain problem $X$ is NP-complete and $P\neq NP$, then $X$ is not polynomial. But we still don't know that $P\neq NP$, so in theory $X$ may be polynomial. Does the fact that $X$ is NP-complete ...
2
votes
0answers
46 views

What is the trick of “adding a huge number” for in the reduction from $\textsf{3-Partition}$?

Problem: To prove the $\textsf{NP-Completeness}$ of the problem of "Packing Squares (with different side length) into A Rectangle", $\textsf{3-Partition}$ is reduced to it, as shown in the following ...
3
votes
0answers
77 views

Relativization of NP-completeness

This is actually exercise 3.7 from "Computational Complexity: A Modern Approach". I need to prove that the NP-Completeness of 3-sat does not relativize, i.e. I need to show that that exists some ...
11
votes
1answer
166 views

Fastest known complexity for combinatorial ILP algorithm?

I'm wondering, what is the best known algorithm, in terms of Big-$O$ notation, to solve Integer Linear Programming? I know that the problem is $NP$-complete, so I'm not expecting anything polynomial. ...
1
vote
1answer
26 views

Reduce Clique to Vertex Cover

I read on the internet that it's possible to reduce Clique to Vertex Cover. Almost everyone use this theorem: if a graph $G$ has a clique of size $k$ then the complement of $G$ has a vertex cover of ...
1
vote
1answer
26 views

SAT-3CNF - Clique [closed]

Could someone show me ( or give me a valuable hint) how to reduce k-Clique problem to SAT-3CNF problem ? I am able to prove reduction from SAT-3CNF to k-Clique, but in the opposite direction it's ...
-2
votes
1answer
64 views

NP-Complete Proof of k sized common set

Input: A set $U= \{w_1, w_2, \ldots, w_n\}$, subsets $S_1, S_2, \ldots, S_m$ of $U$ and integer $k$. Question: Is there a subset with $k$ elements of $U$ which intersects of every $S_i$? Which ...
2
votes
0answers
30 views

reduction of maxcut problem

Show that if the MAX CUT decision problem can be solved in polynomial time so can the MAX CUT optimization problem by writing an algorithm that solves the optimization problem using an algorithm for ...
1
vote
1answer
27 views

Hardness of 3SAT-k

According to these scribe notes (and a paper), 3SAT-5 is NP-hard. The problem is defined to be: given a 3SAT formula, each variable occurs in at most 5 clauses. It is also proven that 3SAT-4 is ...
2
votes
2answers
131 views

Direction of restriction for NP hard proves

I have a very silly question, as I am reading through all the proofs showing a problem is NP hard, one of the techniques is by showing an already-proven NP complete problem is a special case for that ...
1
vote
0answers
91 views

Proof of NP-completeness of a special case of longest-path problem

Problem: Longest Path Input: undirected graph $G= (V, E)$ Question: is there a path with length at least $\frac{|V|}{4}$? I know that in order to prove the simple version of $k$ longest path, we ...
1
vote
0answers
66 views

Is the multiset - subset sum problem variant not in NP?

If the input for a subset sum problem is a multiset (with repetitions) instead of a set (without repetitions), e.g. Set $a = ...
0
votes
3answers
94 views

Given a minimum vertex cover can we find all the others in polynomial time?

Having found one minimum vertex cover of a connected undirected graph, is there a known polynomial-time algorithm for finding all the other minimum vertex covers of the graph, or is this problem ...