Showing that a language is NP Complete (advice)Does FNP-complete = NP-complete?Which NPC problems are NP HardWhy is the class NP-Complete important compared to NP-hard?Showing a problem is NP complete? Reducing CLIQUE to KITE.Is the “modular subset product” problem NP-complete?Do there exist “O(1)-complete” problems?Mahaney's theorem and converting SAT to equivalent languageAre there NP COMPLETE problems that are “easy” in practice?Find a language $L$, such that $L notin mathbfP$, but $L^* in mathbfP$If P = NP, does SAT, or any other NP-Complete poly-reduce to any language different from $emptyset$ or $Sigma^*$?
What are the penalties for overstaying in USA?
Is there any evidence that the small canisters (10 liters) of 95% oxygen actually help with altitude sickness?
Why doesn't a marching band have strings?
Story-based adventure with functions and relationships
Do flight schools typically have dress codes or expectations?
Archery in modern conflicts
Should I tell my insurance company I'm making payments on my new car?
Why does the numerical solution of an ODE move away from an unstable equilibrium?
How can I get more energy without spending coins?
Is this one of the engines from the 9/11 aircraft?
How risky is real estate?
Animation advice please
No IMPLICIT_CONVERSION warning in this query plan
Smooth Julia set for quadratic polynomials
How to split an equation over two lines?
Why do some games show lights shine through walls?
Analog is Obtuse!
Unusual mail headers, evidence of an attempted attack. Have I been pwned?
What happens when your group is victim of a surprise attack but you can't be surprised?
Is it damaging to turn off a small fridge for two days every week?
Going to get married soon, should I do it on Dec 31 or Jan 1?
What is the line crossing the Pacific Ocean that is shown on maps?
How to reply to small talk/random facts in a non-offensive way?
Would a two-seat light aircaft with a landing speed of 20 knots and a top speed of 180 knots be technically possible?
Showing that a language is NP Complete (advice)
Does FNP-complete = NP-complete?Which NPC problems are NP HardWhy is the class NP-Complete important compared to NP-hard?Showing a problem is NP complete? Reducing CLIQUE to KITE.Is the “modular subset product” problem NP-complete?Do there exist “O(1)-complete” problems?Mahaney's theorem and converting SAT to equivalent languageAre there NP COMPLETE problems that are “easy” in practice?Find a language $L$, such that $L notin mathbfP$, but $L^* in mathbfP$If P = NP, does SAT, or any other NP-Complete poly-reduce to any language different from $emptyset$ or $Sigma^*$?
.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty margin-bottom:0;
$begingroup$
I am currently getting ready for my final exam in computational models. I know that there aren't any rules or rule of thumb to show that a language is NP-complete and each problem has its own tricks, but I am really struggling with questions where they give me a language and showing that the language is NP-complete by showing that an NPC problem is polynomial reducible to the given language.
So I wanted to ask for advice. How can I approach such problems? Are there any steps that I can take before to help me somehow? Or is it just literally figuring out which NPC problem is "closest" to the the given language and try to construct a polynomial reduction?
I'd appreciate any advice. Thank you.
complexity-theory
asked Jun 15 at 12:27
Charles CarmichaelCharles Carmichael
1253 bronze badges
$endgroup$
add a comment |
$begingroup$
I am currently getting ready for my final exam in computational models. I know that there aren't any rules or rule of thumb to show that a language is NP-complete and each problem has its own tricks, but I am really struggling with questions where they give me a language and showing that the language is NP-complete by showing that an NPC problem is polynomial reducible to the given language.
So I wanted to ask for advice. How can I approach such problems? Are there any steps that I can take before to help me somehow? Or is it just literally figuring out which NPC problem is "closest" to the the given language and try to construct a polynomial reduction?
I'd appreciate any advice. Thank you.
complexity-theory
asked Jun 15 at 12:27
Charles CarmichaelCharles Carmichael
1253 bronze badges
$endgroup$
add a comment |
$begingroup$
I am currently getting ready for my final exam in computational models. I know that there aren't any rules or rule of thumb to show that a language is NP-complete and each problem has its own tricks, but I am really struggling with questions where they give me a language and showing that the language is NP-complete by showing that an NPC problem is polynomial reducible to the given language.
So I wanted to ask for advice. How can I approach such problems? Are there any steps that I can take before to help me somehow? Or is it just literally figuring out which NPC problem is "closest" to the the given language and try to construct a polynomial reduction?
I'd appreciate any advice. Thank you.
complexity-theory
asked Jun 15 at 12:27
Charles CarmichaelCharles Carmichael
1253 bronze badges
$endgroup$
I am currently getting ready for my final exam in computational models. I know that there aren't any rules or rule of thumb to show that a language is NP-complete and each problem has its own tricks, but I am really struggling with questions where they give me a language and showing that the language is NP-complete by showing that an NPC problem is polynomial reducible to the given language.
So I wanted to ask for advice. How can I approach such problems? Are there any steps that I can take before to help me somehow? Or is it just literally figuring out which NPC problem is "closest" to the the given language and try to construct a polynomial reduction?
I'd appreciate any advice. Thank you.
complexity-theory
complexity-theory
asked Jun 15 at 12:27
Charles CarmichaelCharles Carmichael
1253 bronze badges
asked Jun 15 at 12:27
Charles CarmichaelCharles Carmichael
1253 bronze badges
asked Jun 15 at 12:27
Charles CarmichaelCharles Carmichael
1253 bronze badges
asked Jun 15 at 12:27
Charles CarmichaelCharles Carmichael
1253 bronze badges
asked Jun 15 at 12:27
Charles CarmichaelCharles Carmichael
1253 bronze badges
1253 bronze badges
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Typically, yes, it's a matter of finding a known NP-complete problem that's somehow similar to the one you're trying to work with. So if you're dealing with a problem about formulas, you probably want to reduce some version of SAT or 3SAT to it.
For graph problems, you probably want to reduce some other graph problem. Problems about long paths and cycles probably come from Hamiltonian path/cycle. Problems about classifying vertices into types sound like colouring problems. Problems about graphs containing or not containing some structure might come from clique or independent set. Problems about dividing graphs in two might be Max Cut, or Subset Sum.
Reductions from one type of problem to another are typically more difficult. If you ahve to do that, think about how you can use your target problem to encode things that are needed in the known NP-complete problem. For example, when you reduce 3SAT to independent set, being in or out of the independent set corresponds to being true or false; when you reduce 3SAT to 3-colourability, the three colours you use are "true", "false" and "er, the other colour". But, in these cases, the reduction gadgets tend to be quite fiddly.
Another thing to bear in mind is that, if problem $A$ looks like problem $B$, which you already know to be NP-complete, it might be possible to modify that proof to make it work for $A$. For example, consider 4-colourability. The easy reduction is from 3-colourability: given a graph $G$, add a new vertex, connect that to everything and the new graph is 4-colourable if, and only if, the original graph was 3-colourable. But, if you didn't see that and you knew the reduction from 3SAT to 3-colourability well, it probably wouldn't be very hard to modify that reduction so the four colours were "true", "false", "er, the other colour" and "gee, there are a lot of colours today".
answered Jun 15 at 13:21
David RicherbyDavid Richerby
73.1k16 gold badges114 silver badges202 bronze badges
$endgroup$
$begingroup$
Thank you for the reply! I really appreciate it!
$endgroup$
– Charles Carmichael
Jun 15 at 14:05
add a comment |
Your Answer
StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "419"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);
else
createEditor();
);
function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);
);
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f110715%2fshowing-that-a-language-is-np-complete-advice%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Typically, yes, it's a matter of finding a known NP-complete problem that's somehow similar to the one you're trying to work with. So if you're dealing with a problem about formulas, you probably want to reduce some version of SAT or 3SAT to it.
For graph problems, you probably want to reduce some other graph problem. Problems about long paths and cycles probably come from Hamiltonian path/cycle. Problems about classifying vertices into types sound like colouring problems. Problems about graphs containing or not containing some structure might come from clique or independent set. Problems about dividing graphs in two might be Max Cut, or Subset Sum.
Reductions from one type of problem to another are typically more difficult. If you ahve to do that, think about how you can use your target problem to encode things that are needed in the known NP-complete problem. For example, when you reduce 3SAT to independent set, being in or out of the independent set corresponds to being true or false; when you reduce 3SAT to 3-colourability, the three colours you use are "true", "false" and "er, the other colour". But, in these cases, the reduction gadgets tend to be quite fiddly.
Another thing to bear in mind is that, if problem $A$ looks like problem $B$, which you already know to be NP-complete, it might be possible to modify that proof to make it work for $A$. For example, consider 4-colourability. The easy reduction is from 3-colourability: given a graph $G$, add a new vertex, connect that to everything and the new graph is 4-colourable if, and only if, the original graph was 3-colourable. But, if you didn't see that and you knew the reduction from 3SAT to 3-colourability well, it probably wouldn't be very hard to modify that reduction so the four colours were "true", "false", "er, the other colour" and "gee, there are a lot of colours today".
answered Jun 15 at 13:21
David RicherbyDavid Richerby
73.1k16 gold badges114 silver badges202 bronze badges
$endgroup$
$begingroup$
Thank you for the reply! I really appreciate it!
$endgroup$
– Charles Carmichael
Jun 15 at 14:05
add a comment |
$begingroup$
Typically, yes, it's a matter of finding a known NP-complete problem that's somehow similar to the one you're trying to work with. So if you're dealing with a problem about formulas, you probably want to reduce some version of SAT or 3SAT to it.
For graph problems, you probably want to reduce some other graph problem. Problems about long paths and cycles probably come from Hamiltonian path/cycle. Problems about classifying vertices into types sound like colouring problems. Problems about graphs containing or not containing some structure might come from clique or independent set. Problems about dividing graphs in two might be Max Cut, or Subset Sum.
Reductions from one type of problem to another are typically more difficult. If you ahve to do that, think about how you can use your target problem to encode things that are needed in the known NP-complete problem. For example, when you reduce 3SAT to independent set, being in or out of the independent set corresponds to being true or false; when you reduce 3SAT to 3-colourability, the three colours you use are "true", "false" and "er, the other colour". But, in these cases, the reduction gadgets tend to be quite fiddly.
Another thing to bear in mind is that, if problem $A$ looks like problem $B$, which you already know to be NP-complete, it might be possible to modify that proof to make it work for $A$. For example, consider 4-colourability. The easy reduction is from 3-colourability: given a graph $G$, add a new vertex, connect that to everything and the new graph is 4-colourable if, and only if, the original graph was 3-colourable. But, if you didn't see that and you knew the reduction from 3SAT to 3-colourability well, it probably wouldn't be very hard to modify that reduction so the four colours were "true", "false", "er, the other colour" and "gee, there are a lot of colours today".
answered Jun 15 at 13:21
David RicherbyDavid Richerby
73.1k16 gold badges114 silver badges202 bronze badges
$endgroup$
$begingroup$
Thank you for the reply! I really appreciate it!
$endgroup$
– Charles Carmichael
Jun 15 at 14:05
add a comment |
$begingroup$
Typically, yes, it's a matter of finding a known NP-complete problem that's somehow similar to the one you're trying to work with. So if you're dealing with a problem about formulas, you probably want to reduce some version of SAT or 3SAT to it.
For graph problems, you probably want to reduce some other graph problem. Problems about long paths and cycles probably come from Hamiltonian path/cycle. Problems about classifying vertices into types sound like colouring problems. Problems about graphs containing or not containing some structure might come from clique or independent set. Problems about dividing graphs in two might be Max Cut, or Subset Sum.
Reductions from one type of problem to another are typically more difficult. If you ahve to do that, think about how you can use your target problem to encode things that are needed in the known NP-complete problem. For example, when you reduce 3SAT to independent set, being in or out of the independent set corresponds to being true or false; when you reduce 3SAT to 3-colourability, the three colours you use are "true", "false" and "er, the other colour". But, in these cases, the reduction gadgets tend to be quite fiddly.
Another thing to bear in mind is that, if problem $A$ looks like problem $B$, which you already know to be NP-complete, it might be possible to modify that proof to make it work for $A$. For example, consider 4-colourability. The easy reduction is from 3-colourability: given a graph $G$, add a new vertex, connect that to everything and the new graph is 4-colourable if, and only if, the original graph was 3-colourable. But, if you didn't see that and you knew the reduction from 3SAT to 3-colourability well, it probably wouldn't be very hard to modify that reduction so the four colours were "true", "false", "er, the other colour" and "gee, there are a lot of colours today".
answered Jun 15 at 13:21
David RicherbyDavid Richerby
73.1k16 gold badges114 silver badges202 bronze badges
$endgroup$
Typically, yes, it's a matter of finding a known NP-complete problem that's somehow similar to the one you're trying to work with. So if you're dealing with a problem about formulas, you probably want to reduce some version of SAT or 3SAT to it.
For graph problems, you probably want to reduce some other graph problem. Problems about long paths and cycles probably come from Hamiltonian path/cycle. Problems about classifying vertices into types sound like colouring problems. Problems about graphs containing or not containing some structure might come from clique or independent set. Problems about dividing graphs in two might be Max Cut, or Subset Sum.
Reductions from one type of problem to another are typically more difficult. If you ahve to do that, think about how you can use your target problem to encode things that are needed in the known NP-complete problem. For example, when you reduce 3SAT to independent set, being in or out of the independent set corresponds to being true or false; when you reduce 3SAT to 3-colourability, the three colours you use are "true", "false" and "er, the other colour". But, in these cases, the reduction gadgets tend to be quite fiddly.
Another thing to bear in mind is that, if problem $A$ looks like problem $B$, which you already know to be NP-complete, it might be possible to modify that proof to make it work for $A$. For example, consider 4-colourability. The easy reduction is from 3-colourability: given a graph $G$, add a new vertex, connect that to everything and the new graph is 4-colourable if, and only if, the original graph was 3-colourable. But, if you didn't see that and you knew the reduction from 3SAT to 3-colourability well, it probably wouldn't be very hard to modify that reduction so the four colours were "true", "false", "er, the other colour" and "gee, there are a lot of colours today".
answered Jun 15 at 13:21
David RicherbyDavid Richerby
73.1k16 gold badges114 silver badges202 bronze badges
answered Jun 15 at 13:21
David RicherbyDavid Richerby
73.1k16 gold badges114 silver badges202 bronze badges
answered Jun 15 at 13:21
David RicherbyDavid Richerby
73.1k16 gold badges114 silver badges202 bronze badges
answered Jun 15 at 13:21
David RicherbyDavid Richerby
73.1k16 gold badges114 silver badges202 bronze badges
73.1k16 gold badges114 silver badges202 bronze badges
$begingroup$
Thank you for the reply! I really appreciate it!
$endgroup$
– Charles Carmichael
Jun 15 at 14:05
add a comment |
$begingroup$
Thank you for the reply! I really appreciate it!
$endgroup$
– Charles Carmichael
Jun 15 at 14:05
$begingroup$
Thank you for the reply! I really appreciate it!
$endgroup$
– Charles Carmichael
Jun 15 at 14:05
$begingroup$
Thank you for the reply! I really appreciate it!
$endgroup$
– Charles Carmichael
Jun 15 at 14:05
add a comment |
Thanks for contributing an answer to Computer Science Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f110715%2fshowing-that-a-language-is-np-complete-advice%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
