
Computer Science Computer Science Forum 
 LinkBack  Thread Tools  Display Modes 
May 31st, 2010, 07:49 AM  #1 
Newbie Joined: May 2010 Posts: 2 Thanks: 0  Complexity Theory  Multiple ways to describe a problem
Hi! I get straight to the point: If there are mulitple ways to describe a specific problem, and you can prove that one of those ways is NPComplete, does that mean that the problem is NPComplete or just that the algorithm for this particular way of describing it is? I´m quite sure it´s a stupid question, but I´m stuck with a paper and can´t wrap my head around it Thanks in advance for any answers. 
May 31st, 2010, 10:48 AM  #2 
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 16,046 Thanks: 938 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms  Re: Complexity Theory  Multiple ways to describe a problem
An algorithm can't be NPcomplete, only a problem. If you prove that a problem is NPcomplete, it means that there are no deterministic polynomialtime algorithms to solve it (unless P = NP). But being able to prove that an algorithm for a problem doesn't run in polynomial time doesn't mean that the problem is NPcomplete or even outside of P; there may be a better way of doing it.

May 31st, 2010, 02:21 PM  #3 
Newbie Joined: May 2010 Posts: 2 Thanks: 0  Re: Complexity Theory  Multiple ways to describe a problem
Sorry I think I stated my question rather poorly. Please let me try again. If I can show that my problem can be transformed into an NPComplete problem and I also know that there is no polynominal algorithm to solve it, is this still a case of 'there may be a better way of doing it' , or is it just in NP? I´m asking again because I think thats what my professor was getting at with this assignment. Thank you. 
June 1st, 2010, 05:41 AM  #4  
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 16,046 Thanks: 938 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms  Re: Complexity Theory  Multiple ways to describe a problem Quote:
The usual way of showing that a problem in NP is NPcomplete is to reduce a problem known to be NPhard (e.g., NPcomplete) to it. It's not enough to transform your problem into an instance of a hard problem; you need to transform a hard problem into your problem. SAT is NPcomplete, while 2SAT is in P. It's easy to reduce 2SAT to SAT (zero steps!), but that doesn't show that 2SAT is NPcomplete. If on the other hand you showed that SAT could be reduced in polynomial time to 2SAT that would prove that 2SAT was NPcomplete (and thus that P = NP, a different way to earn your million dollars).  
June 1st, 2010, 11:57 AM  #5 
Senior Member Joined: Oct 2007 From: Chicago Posts: 1,701 Thanks: 3  Re: Complexity Theory  Multiple ways to describe a problem
Of course, if yous how that your problem is equivalent to an NP problem, then you know it's in NP. But part of the proof of equivalence is proving that you can reduce the NP problem to your problem.


Tags 
complexity, describe, multiple, problem, theory, ways 
Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
set theory describe a process  baxy7  Applied Math  1  July 28th, 2010 04:58 PM 
complexity theory {Hamiltonian, DHC, IND}  needlittlehelp01  Computer Science  2  May 17th, 2010 03:05 AM 
complexity theory  complexitytheory  Computer Science  1  December 29th, 2009 03:28 AM 
Complexity of Problem  UnOriginal  Applied Math  2  August 26th, 2009 07:05 AM 
complexity theory  complexitytheory  Complex Analysis  1  December 31st, 1969 04:00 PM 