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
0answers
31 views

Reduction NP-Complete with graph undirected [duplicate]

Given a graph undirected $G=(V,E)$ a subset $I$ of $V$ is indipendent for each couples of vertices u,v in $I$ and {$u,v$} is not in $E$. Prove that the language $L$={$<G,k>$: $k$ is a positive ...
-3
votes
0answers
32 views

Prove that “overlapping edges *through* vertices in a graph” is NP-complete [closed]

Prove That the problem of recover edges(vertex cover) THROUGH Vertices in a graph determines a language NP -complete . Use it for a Demonstration REDUCTION from the language of the NP -complete ...
8
votes
1answer
1k views

Why do Shaefer's and Mahaney's Theorems not imply P = NP?

I'm sure someone has thought about this before or immediately dismissed it, but why does Schaefer's dichotomy theory along with Mahaney's theorem on sparse sets not imply P = NP ? Here's my ...
0
votes
0answers
24 views

NP-Hard vs NP-Complete Why NP-complete so important? [duplicate]

A problem $L$ is NP-complete when:- $L\in \text{NP}$ For every problem $L' \in \text{NP}$, $L'$ is polynomial time reducible to $L$ When at least property 2 is satisfied for a problem $L$ (but ...
1
vote
0answers
48 views

Calculating Time Complexity of Quadratic Diophantine Equation

The particular quadratic Diophantine equation: $$ R(a,b,c) \Leftrightarrow \exists X \exists Y :aX^2 + bY - c = 0 $$ is NP-complete. (a, b, and c are given in their binary representations. a, b, c, ...
2
votes
2answers
69 views

What is practical difference between NP and PSPACE-complete?

Here's something that has puzzled me lately, and perhaps someone can explain what I'm missing. Problems in NP are those that can be solved on a NDTM in polynomial time. Now assuming P$\,\neq\,$NP, ...
-1
votes
0answers
27 views

How can I prove that Clique Problem is NP-complete using TSP

I would like to know if there is a way to prove that Clique problem is NP-Complete, using TSP. In order to prove that Clique is NP-Complete, I know that first I have to prove that Clique is NP. Then ...
2
votes
1answer
59 views

Prove Vertex-Cover of maximum degree 3 is NPC

This is a homework question. I need to prove that the following language is in NP Complete: 3-VERTEX-COVER = $\{\langle G,k\rangle \mid$ G is an undirected graph, each vertex in $G$ has at most ...
10
votes
3answers
851 views

Why is the class of NPC important compared to NP-hard?

I'm studying computational complexity and I was wondering why NPC is an important class at all. I find it obvious why we're interested in showing a given NP problem is NP-hard. I also understand ...
1
vote
1answer
138 views

If the decision problem can be solved in poly time, show the optimization problem also can [duplicate]

Here is a problem I am trying to solve: The bin packing decision problem is defined as follows: given an unlimited number of bins, each of capacity equal to $1$, and $n$ objects with sizes ...
1
vote
1answer
40 views

Quadratic Diophantine equation - Polynomial Time Cases

In number theory, solving a Quadratic Diophantine equation (a, b, c constants) $$ a*x^2+b*y= c $$ is an NP-Complete problem. Even for a=1, the problem remains NP-Complete. The solution (x, y) are ...
2
votes
1answer
31 views

A Query regarding Quadratic Residuocity Problem

In number theory, an integer q is called a quadratic residue modulo n if it is congruent to a perfect square modulo n; i.e., if there exists an integer x such that: $$ x^2\equiv q \pmod{n}. ...
1
vote
0answers
14 views

A query regarding the Max3SAT Approximation Algorithm's Application

Its known that a polynomial time Approximation Algorithm that satisfies 3MaxSAT in 7/8+e clauses implies P=NP. If given that the given 3MaxSAT is satisfiable, it is still difficult to find a 7/8+e ...
2
votes
1answer
57 views

The initial NP-complete problem

It is always claimed that Cook and Levin gives the very first NP-complete problem and proof of it. But when I look at the actual proof I think what Cook and Levin did was reduced (or transformed) SAT ...
4
votes
2answers
670 views

Why does Schaefer's theorem not prove that P=NP?

This is probably a stupid question, but I just don't understand. In another question they came up with Schaefer's dichotomy theorem. To me it looks like it proves that every CSP problem is either in P ...
5
votes
3answers
99 views

Is 2-SAT with XOR-relations NP-complete?

I'm wondering if there is a polynomial algorithm for "2-SAT with XOR-relations". Both 2-SAT and XOR-SAT are in P, but is its combination? Example Input: 2-SAT part: ...
3
votes
1answer
43 views

Proving NP completness without reductions

What methods are there to prove a language is NP-complete? I already know the reduction method, but are there more sophisticated/advanced methods to prove this?
1
vote
1answer
24 views

How does derandomization of 3SAT work via conditional expectations?

Given a single SAT clause with its 3 literals coming from 3 different variables it is obvious that a random assignment of values will satisfy it with probability 7/8 But I do not understand how ...
-1
votes
1answer
145 views

How to prove a Double CNF SAT is in NP [duplicate]

So I've been stuck trying to figure this problem out for a while. I've looked on wikis and all over stack exchange but I'm really stumped. This isn't my best subject, so any sort of explanation would ...
5
votes
1answer
229 views

Is set cover still NP-complete if you have a given k?

Set cover is NP-complete given an arbitrary set $U$, a set $S$ of subsets of $U$, and an integer $k$. However, what if $k$ is always a constant 3? Is that problem still NP-complete?
2
votes
2answers
42 views

Difficult Cases for 3MaxSAT and 3SAT Approximation Algorithm

Its known that a polynomial time approximation algorithm that satisfies 3MaxSAT in 7/8+e clauses implies P=NP. Its also experimentally known that 3SAT has the most difficult known cases when the ...
3
votes
1answer
44 views

Is it NP complete to decide whether a graph has bigger clique or bigger independence number?

Is it $\mathsf{NP}$ complete to decide whether a graph $G$ has bigger clique $\omega(G)$ or bigger independence number $\alpha(G)$?
1
vote
1answer
60 views

Seeking Efficient Approximation Algorithm for Adaptation of TSP

Consider the following adaptation of the traveling salesman problem: Given a complete, undirected graph $G$ with nonnegative edge weights, color each vertex either red or blue. Find the shortest ...
-1
votes
1answer
81 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 ...
3
votes
1answer
56 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
56 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
165 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
68 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
67 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 ...
4
votes
1answer
179 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 ...
2
votes
1answer
80 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
90 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
58 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
38 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
67 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
114 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
75 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
80 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
52 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
70 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
1answer
61 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
1answer
93 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
84 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
191 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
386 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
72 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
65 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
31 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
74 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\}$ ...