My Math Forum  

Go Back   My Math Forum > Science Forums > Computer Science

Computer Science Computer Science Forum


Reply
 
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 NP-Complete, does that mean that the problem is NP-Complete or just that the algorithm for this particular way of describing it is? Im quite sure its a stupid question, but Im stuck with a paper and cant wrap my head around it

Thanks in advance for any answers.
mcaos is offline  
 
May 31st, 2010, 10:48 AM   #2
Global Moderator
 
CRGreathouse's Avatar
 
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.
CRGreathouse is offline  
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?

Im asking again because I think thats what my professor was getting at with this assignment.

Thank you.
mcaos is offline  
June 1st, 2010, 05:41 AM   #4
Global Moderator
 
CRGreathouse's Avatar
 
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).
CRGreathouse is offline  
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.
cknapp is offline  
Reply

  My Math Forum > Science Forums > Computer Science

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





Copyright © 2019 My Math Forum. All rights reserved.