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

0
votes
0answers
15 views

sheduling in parallel machines with machine delay and job constraints

Given m machines and n jobs ,we want to schedule jobs into machines ,such that lateness ie( idealCompletionTime- actualCompletionTime) is minimized .Also the machines are required to take a break ...
4
votes
0answers
45 views

2 Dimensional Subset Sum: looking for information

I do not know if this problems exists with a different name, if it is, I could not find it. The problem is this: Given a set $S$ of $n$ points in $\mathbb{Z}^2$, is there a subset $A\subset S$ ...
3
votes
2answers
351 views

Is it allowed to do a binary search with an oracle when proving NP-completeness?

In http://cs.stackexchange.com/a/45524/28999, they do a binary search using an oracle for an NP-Complete problem. They show that the original problem can be reduced to that NP-Complete problem, ...
3
votes
2answers
102 views

Is my theorem about $P \neq NP$ correct? [closed]

It is known that there are problems in P that, provably, are not solvable in less than $O(N^k)$, for some $k$. Now consider some infinite set $K \subseteq \mathbb{R}^+_0$ such as K is unbounded from ...
1
vote
2answers
93 views

If an NP-complete problem is shown to have a non-polynomial lower bound, would that prove that P != NP?

I understand that the Cook-Levin theorem proved that any NP problem is reducible to an NP-complete problem, which signifies that if a polynomial-time algorithm for an NP-complete problem is found, it ...
1
vote
1answer
30 views

Are non-trivial sets formed by set operations on NPC sets still in NPC?

I know that from this answer to a question on the class NPC, that NPC is not in general closed under intersection and union. However, the answer used languages which form trivial languages under ...
4
votes
1answer
47 views

looking for a strongly NP Complete related problem

I'm looking for a problem that is NP-Complete (even) if the number of input values is at most a polylog of the input size. So some or each value in the input should be so large that the number of ...
3
votes
1answer
77 views

Covering a polygon with n circular rings

Question 1: Why we can/can't solve the following problem using a geometric constraint solver? Question 2: Is there any algorithm to solve this problem? Question 3: Can we reduce this problem into some ...
0
votes
1answer
94 views

Clique decision problem restricted to a subgraph [closed]

I know that the clique problem is NP-complete. However, what if we change the problem a little bit? For example, Given a graph $G(V,E)$, an integer $k$ and a subset $S$ of $m$ vertices, we are ...
1
vote
1answer
23 views

Shaefer's Dichotomy Theorem [duplicate]

Could you please resolve a confusion with Schaefer's theorem for me? Namely, why does it not imply many problems in P are NP-complete? For example, primality testing surely cannot be reduced to one of ...
1
vote
1answer
52 views

NP Complete Subset GCD Proof

$SubsetGCD$ is described by the following: instance: A set of positive integers $S$ and an integer $k$ question: does there exist a subset $S'$ of $S$ of size $k$ such that $GCD(S') = GCD(S)$ ...
0
votes
0answers
42 views

Existence of randomized reduction but no deterministic reduction

What is the consequence to complexity theory of having a randomized reduction from an NP-complete problem to problem $\Pi$ while there is no deterministic reduction from an NP-complete problem to ...
0
votes
1answer
47 views

Reduction of SUBSET-SUM to SET-PARTITION [duplicate]

There is a similar question that has been asked, but my question addresses particular detail of an answer. I am trying to reduce SUBSET-SUM to SET-PARTITION. I found the following description: ...
2
votes
1answer
32 views

Help Understanding the Type and Complexity of my Programming Task [closed]

I'm working on a programming task that I, without good evidence, have a sneaking suspicion is NP-Complete. With that said, I would like confirmation on this if possible, as well as some suggestion for ...
1
vote
0answers
33 views

Computational Complexity of Longest Common Subsequence Problem Variation? [closed]

The general Longest common sub-sequence problem over alphabet size = 2 (0,1) is NP Complete. What is the Computational Complexity of the problem if these additional constraints are imposed on the ...
3
votes
1answer
53 views

How to Prove NP-Completeness of Minimum Crossing Problem?

In graph theory, the crossing number cr(G) of a graph G is the lowest number of edge crossings of a plane drawing of the graph G. (from wikipedia) I know that the problem of counting the ...
9
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
26 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
50 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
75 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, ...
2
votes
1answer
67 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 ...
12
votes
3answers
921 views

Why is the class NP-Complete important compared to NP-hard?

I'm studying computational complexity and I was wondering why the NP-Complete (NPC) problems is an important class at all. I find it obvious why we're interested in showing a given NP problem is ...
1
vote
1answer
145 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
46 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
36 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
66 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
683 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 ...
6
votes
3answers
127 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
45 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
27 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
170 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
240 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
51 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
69 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
87 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
59 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
60 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
172 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
87 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
68 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
190 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
82 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
123 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
68 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
39 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
73 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
122 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 ...