http://wiki.karljones.com/index.php?action=history&feed=atom&title=NP-completeness 2026-10-23T15:07:41Z Revision history for this page on the wiki MediaWiki 1.24.2 http://wiki.karljones.com/index.php?title=NP-completeness&diff=12622&oldid=prev 2016-04-22T01:24:10Z

<p>‎<span dir="auto"><span class="autocomment">External links</span></span></p> <table class='diff diff-contentalign-left'> <col class='diff-marker' /> <col class='diff-content' /> <col class='diff-marker' /> <col class='diff-content' /> <tr style='vertical-align: top;'> <td colspan='2' style="background-color: white; color:black; text-align: center;">← Older revision</td> <td colspan='2' style="background-color: white; color:black; text-align: center;">Revision as of 01:24, 22 April 2016</td> </tr><tr><td colspan="2" class="diff-lineno">Line 30:</td> <td colspan="2" class="diff-lineno">Line 30:</td></tr> <tr><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td></tr> <tr><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* [https://en.wikipedia.org/wiki/NP-completeness NP-completeness] @ Wikipedia</div></td><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* [https://en.wikipedia.org/wiki/NP-completeness NP-completeness] @ Wikipedia</div></td></tr> <tr><td colspan="2">&#160;</td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr> <tr><td colspan="2">&#160;</td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">[[Category:Complexity]]</ins></div></td></tr> <tr><td colspan="2">&#160;</td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">[[Category:Computation]]</ins></div></td></tr> </table>

Karl Jones http://wiki.karljones.com/index.php?title=NP-completeness&diff=9121&oldid=prev 2016-02-29T17:43:42Z

<p>‎<span dir="auto"><span class="autocomment">See also</span></span></p> <table class='diff diff-contentalign-left'> <col class='diff-marker' /> <col class='diff-content' /> <col class='diff-marker' /> <col class='diff-content' /> <tr style='vertical-align: top;'> <td colspan='2' style="background-color: white; color:black; text-align: center;">← Older revision</td> <td colspan='2' style="background-color: white; color:black; text-align: center;">Revision as of 17:43, 29 February 2016</td> </tr><tr><td colspan="2" class="diff-lineno">Line 24:</td> <td colspan="2" class="diff-lineno">Line 24:</td></tr> <tr><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* [[Computational complexity theory]]</div></td><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* [[Computational complexity theory]]</div></td></tr> <tr><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* [[Computer science]]</div></td><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* [[Computer science]]</div></td></tr> <tr><td colspan="2">&#160;</td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">* [[Parallel computation with molecular-motor-propelled agents in nanofabricated networks]]</ins></div></td></tr> <tr><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* [[P versus NP problem]]</div></td><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* [[P versus NP problem]]</div></td></tr> <tr><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td></tr> </table>

Karl Jones http://wiki.karljones.com/index.php?title=NP-completeness&diff=9117&oldid=prev 2016-02-29T17:41:53Z

<p>Created page with &quot;In <a href="/index.php/Computational_complexity_theory" title="Computational complexity theory">computational complexity theory</a>, a <a href="/index.php/Decision_problem" title="Decision problem">decision problem</a> is &#039;&#039;&#039;NP-complete&#039;&#039;&#039; when it is both in NP and NP-hard. The set of NP-complete problems is often denoted by NP-...&quot;</p> <p><b>New page</b></p><div>In [[computational complexity theory]], a [[decision problem]] is '''NP-complete''' when it is both in NP and NP-hard.<br /> <br /> The set of NP-complete problems is often denoted by NP-C or NPC.<br /> <br /> The abbreviation NP refers to &quot;nondeterministic polynomial time&quot;.<br /> <br /> == Description ==<br /> <br /> Although any given solution to an NP-complete problem can be verified quickly (in polynomial time), there is no known efficient way to locate a solution in the first place<br /> <br /> Indeed, the most notable characteristic of NP-complete problems is that no fast solution to them is known.<br /> <br /> That is, the time required to solve the problem using any currently known algorithm increases very quickly as the size of the problem grows.<br /> <br /> As a consequence, determining whether or not it is possible to solve these problems quickly, called the [[P versus NP problem]], is one of the principal unsolved problems in computer science today.<br /> <br /> While a method for computing the solutions to NP-complete problems using a reasonable amount of time remains undiscovered, computer scientists and programmers still frequently encounter NP-complete problems.<br /> <br /> NP-complete problems are often addressed by using [[heuristic methods]] and [[approximation algorithms]].<br /> <br /> == See also ==<br /> <br /> * [[Algorithm]]<br /> * [[Computational complexity theory]]<br /> * [[Computer science]]<br /> * [[P versus NP problem]]<br /> <br /> == External links ==<br /> <br /> * [https://en.wikipedia.org/wiki/NP-completeness NP-completeness] @ Wikipedia</div>

Karl Jones