Revisions to NP-complete variants of NPI problems

replaced http://cstheory.stackexchange.com/ with https://cstheory.stackexchange.com/

Source Link

edited Apr 13, 2017 at 12:32

Motivated by these posts, An NP-complete variant of factoring An NP-complete variant of factoring and Relationship between symmetry and computational intractability Relationship between symmetry and computational intractability, It seems to be worthwhile to investigate the different factors that increase the hardness of problems in NPI. I'm interested in other NP-complete variants of problems of intermediate complexity.

Is there a recent survey paper of $NP$-complete variants of problems of intermediate complexity (problems between P and NP-complete)?

UPDATE: Bounty may be awarded to an answer that gives other interesting NPI problems that have an $NP$-complete variant.

Bounty Ended with no winning answer by Mohammad Al-Turkistany

occurred Jul 4, 2011 at 11:22

tag is added

Link

edited Jun 27, 2011 at 10:59

added 124 characters in body

Source Link

edited Jun 27, 2011 at 10:44

Motivated by these posts, An NP-complete variant of factoring and Relationship between symmetry and computational intractability, It seems to be worthwhile to investigate the different factors that increase the hardness of problems in NPI. I'm interested in other NP-complete variants of problems of intermediate complexity.

Is there a recent survey paper of $NP$-complete variants of problems of intermediate complexity (problems between P and NP-complete)?

UPDATE: Bounty may be awarded to an answer that gives other interesting NPI problems that have an $NP$-complete variant.

Bounty Started worth 100 reputation by Mohammad Al-Turkistany

occurred Jun 27, 2011 at 10:32

added 5 characters in body

Source Link

edited Jun 23, 2011 at 15:52

Loading

added 135 characters in body

Source Link

edited Jun 23, 2011 at 15:46

Loading

Source Link

asked Jun 23, 2011 at 15:41

Loading

Return to Question