Notices
Results 1 to 4 of 4

Thread: proving something in NP

  1. #1 proving something in NP 
    New Member
    Join Date
    Mar 2014
    Posts
    2
    Hi,

    I have a new graph problem which, due to its similarities to other known problems, I'm fairly certain that it is contained in NP and is NP-hard (the 2 necessary ingredients for NP-completeness). I have a proof that it is NP-hard, however, proving that it's contained in NP is turning out to be difficult.

    My understanding of the normal process for doing this is to prove either reducibility from both directions or to prove that, given a potential solution, the solution can be verified in polynomial time.

    I have a potential solution and a proof that the solution can be verified in NP time (using a known NP-complete problem). My question is: Is that sufficient to prove that my problem is in NP?

    My gut says no, but various burritos have remarked to me that my gut is not always correct.

    Thanks in advance for any help.


    Reply With Quote  
     

  2.  
     

  3. #2  
    Forum Radioactive Isotope MagiMaster's Avatar
    Join Date
    Jul 2006
    Posts
    3,440
    Reducibility in one direction is basically used to show that the problem is NP, so that can usually be skipped if you have a good proof for it already. And NP means that it can be verified in polynomial time, not in NP time (which isn't actually a thing). If you need to use a solve an NP-complete problem to verify your solution, your problem probably isn't NP. (The usual thing is to make it so that solving some NP-complete problem provides a solution to your problem with minimal further work.)

    The other thing is, being both NP and NP-hard isn't quite enough for NP-completeness (IIRC). The last thing is that if you could solve the new problem, you could solve all NP problems. This comes free with the proof by reduction. On the other hand, the chances of something being NP and NP-hard but not NP-complete seems slim and there may be some proof out there that no such thing exists (which would mean that proving something NP and NP-hard would automatically imply NP-completeness).


    Reply With Quote  
     

  4. #3  
    New Member
    Join Date
    Mar 2014
    Posts
    2
    Thanks for the response, but I'm sorry to say that you do not recall correctly. With the possible exception of the original SAT proofs that defined the concepts of NP and NP-hardness, the primary way to prove that something is NP-complete is to prove that 1. it is contained in the set NP, and 2. that a known NP-complete problem is reducible to it, which proves that it is at least as hard as NP-complete problems (aka NP-hard).
    just proving the 2nd could still mean that it is in a class that contains NP such as EXP.

    As I mentioned, proving reducibility in both directions would prove that it's NP-complete, but I don't yet have a way to prove that my problem is reducibile to a known NP-complete problem, only the other way around.
    here's a link to more basic information for you on proving NP-completeness:
    stackoverflow.com/questions/4294270/how-to-prove-that-a-problem-is-np-complete
    Reply With Quote  
     

  5. #4  
    Forum Radioactive Isotope MagiMaster's Avatar
    Join Date
    Jul 2006
    Posts
    3,440
    I may be remembering the definition of NP-hard wrong, but NP-complete does mean that a solution to that problem would also be a solution to all other NP problems.

    This was proven the hard way for the original SAT problem. All other NP-complete problems were then shown to reduce to SAT, which means that a solution to SAT would solve the other problem and vice versa. This is an important property (really, the defining property) of NP-complete problems.

    Now, what I may be remembering wrong is whether or not the definition of NP-hard includes the "this could solve all NP problems" bit, but now that I think about it a bit, I'm pretty sure it does. It's a moot point anyway because you've already proven that part.

    As for the first part, reducing your problem to an NP-complete problem is one way of proving it NP, but not the only way. To prove something is NP directly you need to demonstrate an algorithm that given a problem and a solution you can verify that that solution works for that problem in polynomial time.
    Reply With Quote  
     

Similar Threads

  1. Proving the non-existence of god?
    By Zwirko in forum Scientific Study of Religion
    Replies: 138
    Last Post: October 20th, 2012, 08:54 PM
  2. Proving you all exist.
    By 15uliane in forum Philosophy
    Replies: 25
    Last Post: October 29th, 2011, 05:52 PM
  3. proving coplanarity
    By scientist91 in forum Mathematics
    Replies: 6
    Last Post: March 14th, 2010, 04:03 AM
  4. Proving God.
    By Cat1981(England) in forum Scientific Study of Religion
    Replies: 100
    Last Post: November 3rd, 2007, 08:39 PM
  5. Proofs and Proving
    By Wilhelm in forum Mathematics
    Replies: 3
    Last Post: December 19th, 2006, 12:18 PM
Tags for this Thread

View Tag Cloud

Bookmarks
Bookmarks
Posting Permissions
  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •