Does NP-Completeness Transfer in Polynomial Reductions?

  • Thread starter theholtzmann
  • Start date
In summary, if A is NP-complete and can be transformed into B in polynomial time, then B is also NP-complete. However, if B is NP-complete, it does not necessarily mean that A is also NP-complete.
  • #1
theholtzmann
1
0

Homework Statement


The problem asks that if I was able to transform from problem A to problem B in polynomial time, and they ask...

First question, If I know A and B are both in NP... and if I know (somehow) that A is NP complete, does that imply B is NP complete?

Second question here, if I know(somehow) B is NP-complete, does that imply A is NP-complete?


Homework Equations





The Attempt at a Solution


From what I understand, the only way to know a problem is NP-complete is if I know it is NP-hard, I have a poly-time verifier, and I can reduce it from another NP-Complete problem in poly-time.

This would tell me that the first question, where I know A is NP-Complete, the fact I could translate it in poly-time into B would imply B is NP-complete, since I know B is in NP as well

For the second question, If I know B is NP-complete, I think that does not necessarily mean A is NP complete, since every tree I see derived NP-complete problems from SAT only have unidirectional arrows, (Clique from SAT or VertexCover from Clique, but not viceversa in either case I've seen...)

I need to understand how this works both ways, if at all... or if I'm even on the right track...
Thanks in advance.
 
Physics news on Phys.org
  • #2




Hello there! As a fellow scientist, I can help shed some light on your questions.

Firstly, yes, if A is NP-complete and you are able to transform it into B in polynomial time, then B is also NP-complete. This is because all NP-complete problems are reducible to each other in polynomial time. Therefore, if A is NP-complete, then B must also be NP-complete since it can be reduced to A in polynomial time.

For your second question, if B is NP-complete, it does not necessarily mean that A is also NP-complete. This is because NP-completeness is a property of individual problems, not a relationship between two problems. Just because B can be reduced to A in polynomial time does not automatically mean that A is also NP-complete.

I hope this helps clarify your understanding. Keep up the good work in your scientific pursuits!
 

Related to Does NP-Completeness Transfer in Polynomial Reductions?

1. What is NP-Completeness?

NP-Completeness is a concept in computational complexity theory that refers to the difficulty of solving a problem. Specifically, it pertains to decision problems that cannot be solved in polynomial time, but can be verified in polynomial time. These problems are considered the most challenging in computer science.

2. What are reductions in NP-Completeness?

Reductions in NP-Completeness refer to a method used to show that a problem is NP-Complete. This involves transforming a known NP-Complete problem into the problem in question, and showing that if the second problem can be solved in polynomial time, then so can the first problem.

3. Why are reductions important in NP-Completeness?

Reductions are important in NP-Completeness because they allow us to classify problems as NP-Complete without having to individually prove each one. By reducing a problem to a known NP-Complete problem, we can establish that the problem is at least as difficult as an NP-Complete problem.

4. How are reductions used in practice?

In practice, reductions are used to classify real-world problems as NP-Complete. This helps in identifying the complexity of a problem, and can guide the development of more efficient algorithms to solve it. Additionally, reductions are used in the design of approximation algorithms, which provide approximate solutions to NP-Complete problems in a shorter amount of time.

5. Are there any limitations to reductions in NP-Completeness?

While reductions are a powerful tool in identifying NP-Complete problems, there are limitations to their use. One limitation is that the reduction must be polynomial time, meaning it cannot take an excessive amount of time to transform the problem. Additionally, some problems may not have a known NP-Complete problem to reduce from, making it difficult to classify their complexity.

Similar threads

Proof of NP-completeness via reduction
    • Engineering and Comp Sci Homework Help
Replies
1
Views
1K
I Are electrons universal problem solvers?
    • Quantum Physics
Replies
4
Views
832
Cook's theorem breaks down under some oracle A
    • Engineering and Comp Sci Homework Help
Replies
1
Views
1K
Graph Contractability: NP-Complete or Not?
    • Engineering and Comp Sci Homework Help
Replies
4
Views
2K
Continuous-time loop computer for NP problems?
    • Programming and Computer Science
Replies
5
Views
2K
MHB Is HSC NP-Complete in Graph Theory?
    • Set Theory, Logic, Probability, Statistics
Replies
1
Views
1K
MHB Is the Subgraph Isomorphism problem NP-complete?
    • Programming and Computer Science
Replies
1
Views
2K
A question about the Cook-Levin Theorem
    • General Math
Replies
4
Views
1K
MHB Solving Decision Problem with k Colors - NP-Complete
    • Programming and Computer Science
Replies
6
Views
2K
Showing NP-completeness of longest path problem
    • Calculus and Beyond Homework Help
Replies
4
Views
2K

Hot Threads

Recent Insights

Back
Top