 My Math Forum Complexity Theory - Multiple ways to describe a problem
 User Name Remember Me? Password

 Computer Science Computer Science Forum

 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 NP-Complete, does that mean that the problem is NP-Complete 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 NP-complete, only a problem. If you prove that a problem is NP-complete, it means that there are no deterministic polynomial-time 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 NP-complete 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 NP-Complete 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:
 Originally Posted by mcaos If I can show that my problem can be transformed into an NP-Complete 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?
If you can prove that your problem is in NP (that is, can be verified in polynomial time) and that there are no polynomial-time algorithms to solve it, you've solved the P vs. NP problem and should collect \$1 million from the Clay Institute (two years following your publication in a prestigious journal).

The usual way of showing that a problem in NP is NP-complete is to reduce a problem known to be NP-hard (e.g., NP-complete) 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 NP-complete, while 2-SAT is in P. It's easy to reduce 2-SAT to SAT (zero steps!), but that doesn't show that 2-SAT is NP-complete. If on the other hand you showed that SAT could be reduced in polynomial time to 2-SAT that would prove that 2-SAT was NP-complete (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 Show Printable Version Email this Page Display Modes Linear Mode Switch to Hybrid Mode Switch to Threaded Mode Similar Threads Thread Thread Starter Forum Replies Last Post baxy7 Applied Math 1 July 28th, 2010 04:58 PM needlittlehelp01 Computer Science 2 May 17th, 2010 03:05 AM complexitytheory Computer Science 1 December 29th, 2009 03:28 AM UnOriginal Applied Math 2 August 26th, 2009 07:05 AM complexitytheory Complex Analysis 1 December 31st, 1969 04:00 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top      