Questions on the topic of NP-Completeness, which comes from Theoretical Computer Science
Questions tagged [np-complete]
676 questions
15
votes
6 answers
Example of a problem that is NP-Hard but not NP-Complete
Please, mention one problem that is NP-Hard but not NP-Complete? And, explain why.
I see some papers assert Degree Constrained Minimum Spanning Tree is an NP-Hard problem and some say it's NP-Complete. Why so? Is it something that we don't have a…
user1869
9
votes
2 answers
Can any NP-Complete problem can be reduced to any other NP-Complete problem in polynomial time?
Is it true to say that any NP-Complete problem can be reduced to any other NP-Complete problem in polynomial time?
Badger
- 229
8
votes
5 answers
How to prove that $P \neq NP$
How to prove that $P \neq NP$?
To prove that $P = NP$ all we need to do is to solve one NP-Complete problem in polynomial time for any input, and because all the NP-Complete problems have reduction from one to each other we can say $P = NP$.
What…
Ilya Gazman
- 1,440
6
votes
2 answers
How do I reduce 3-SAT to a 3-SAT NAE problem?
I am trying to figure out how to reduce a 3SAT problem to a 3SAT NAE (Not All Equal) problem.
Not only that, I also figure out that I am not so sure about the reduction to 3SAT either.
Anyway, how do I go for that?
Since the size of each clause is…
N3sh
- 181
6
votes
2 answers
Why one of NP-Complete problem had a polynomial solution then everyone of them has?
Each NP problem is different, if one (even the hardest one) NP problem could be solved in polynomial time, I guess some related NP problems that could reduced to this one could also be solved in polynomial time. But why all? Does that mean all of…
user1532146
- 115
6
votes
1 answer
Is half-filled magic square problem NP-complete?
Here is the problem:
We have a square with some numbers from 1..N in some cells. It's needed to determine if it can be completed to a magic square.
Examples:
2 _ 6 2 7 6
_ 5 1 >>> 9 5 1
4 3 _ 4 3 8
7 _ _
9 _ _ >>> NO SOLUTION
8 _…
levanovd
- 165
5
votes
1 answer
P vs NP explanation on wikipedia
I'm reading the page under http://simple.wikipedia.org/wiki/P_versus_NP, which states:
"...people want to know if there are any NP problems that are not P
problems. That means they would like to know if there are any problems
where the answer…
Phillip
- 153
3
votes
1 answer
Prove Max-cut problem is NPC
MaxCut problem:
Given an undirected graph G(V,E), find a cut between the vertices, such that the number of edges crossing the cut is maximal.
Example:
How can I prove that this is NPC problem?
This is homework, I know I should show you what I have…
user75715
- 31
3
votes
1 answer
Is Integer Linear Programming a special case of Linear Programming
As known, LP is solvable in polynomial time, and ILP seems to a special case of LP, why it is NP complete?
Oliver Hu
- 31
3
votes
1 answer
Definition of NP
I understand that NP describes the class of problems to which the solutions can be verified in polynomial time, but I have trouble understanding its definition. The below is my book's definition:
We say that B is an efficient certifier for a problem…
user8969
3
votes
1 answer
For two problems A and B, if A is in P, then A is reducible to B?
For any two problems A and B, if A is in P(complexity) then A is reducible to B.
Could anyone explain why this is true?
Takkun
- 433
2
votes
1 answer
NP question - how to reduce this Graph problem?
I am losing my head on Algorithms (namely P-NP stuff) and I thought I would pop over here.
I have a question: in my last exam (which went rather bad :/ ) there was a question which was on the line "given a graph G(V,E), can we check whether it has…
N3sh
- 181
2
votes
1 answer
how to find a solution of an np complete problem given a solution to another np complete problem?
Is it correct to say that give a solution (with any time complexity) to an NP-Complete problem it can be modified in some way so that it can solve all NP-Complete problems? If yes, then how can that be done?
M.Hamza Ali
- 343
2
votes
0 answers
Filling a big rectangle with small rectangles
There are N numbers; their values are A1, A2, ..., An respectively, their sum is S. There is a big rectangle which area is S. You need to draw N number small rectangle which area is its value.
Requirement:
(1). The small rectangle must be inside…
code1995
- 21
2
votes
1 answer
Prove Factoring is in NP
INPUT: an integer $n$ and a integer $d$
QUESTION: does $n$ have a prime factor less than $d$?
Does a polynomial time algorithm exist that can tell whether or not $n$ has a prime factor $< d$?
Would iterating through all possible primes $< d$ take…
Takkun
- 433