https://complexityzoo.net/index.php?title=Complexity_Garden&feed=atom&action=history
Complexity Garden - Revision history
2024-03-29T13:19:41Z
Revision history for this page on the wiki
MediaWiki 1.35.0
https://complexityzoo.net/index.php?title=Complexity_Garden&diff=6887&oldid=prev
A3nm: /* #WSAT: Weighted SAT */ -blank line
2023-10-26T20:34:33Z
<p><span dir="auto"><span class="autocomment">#WSAT: Weighted SAT: </span> -blank line</span></p>
<table class="diff diff-contentalign-left diff-editfont-monospace" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="en">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 20:34, 26 October 2023</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l100" >Line 100:</td>
<td colspan="2" class="diff-lineno">Line 100:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Memberships: &#8712; {{zcls|symbols|sharpwt|#WT}}</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Memberships: &#8712; {{zcls|symbols|sharpwt|#WT}}</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>----</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>----</div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del style="font-weight: bold; text-decoration: none;"></del></div></td><td colspan="2"> </td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>===== <span id="3sum" style="color:red">3SUM</span>: Do there exist members of a list satisfying <math>a+b+c=0</math>? =====</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>===== <span id="3sum" style="color:red">3SUM</span>: Do there exist members of a list satisfying <math>a+b+c=0</math>? =====</div></td></tr>
</table>
A3nm
https://complexityzoo.net/index.php?title=Complexity_Garden&diff=6747&oldid=prev
Quackack: /* The Problems */
2021-12-18T05:52:03Z
<p><span dir="auto"><span class="autocomment">The Problems</span></span></p>
<table class="diff diff-contentalign-left diff-editfont-monospace" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="en">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 05:52, 18 December 2021</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l168" >Line 168:</td>
<td colspan="2" class="diff-lineno">Line 168:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>----</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>----</div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; 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"> </td><td class='diff-marker'>+</td><td style="color: #202122; 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;">===== <span id="coloring" style="color:red">Coloring</span>: Color a Graph So Adjacent Vertices Have Different Colors =====</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; 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;">The input is a graph, G, with a number of colors, C. The output is whether there exists an assignment of each vertex to one of C colors so that no two adjacent vertices have the same color. If such an assignment exists, we say G is C-colorable. C-coloring is the problem of determining if a graph is C colorable.</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; 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"> </td><td class='diff-marker'>+</td><td style="color: #202122; 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;">Even 3-Coloring is NP hard. For some &epsilon, it is NP hard to even find a 3-coloring where only an &epsilon fraction of edges have the same colors on both sides.</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; 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"> </td><td class='diff-marker'>+</td><td style="color: #202122; 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;">Variations on this problem may also ask for the coloring, or the minimum C so that a graph is C-colorable.</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; 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"> </td><td class='diff-marker'>+</td><td style="color: #202122; 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;">Algorithms: ?</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; 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"> </td><td class='diff-marker'>+</td><td style="color: #202122; 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;">Memberships: &#8712; [[Complexity Zoo#npc|NP-complete]]</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; 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"> </td><td class='diff-marker'>+</td><td style="color: #202122; 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"> </td><td class='diff-marker'>+</td><td style="color: #202122; 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 class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>{{Garden-Problem</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>{{Garden-Problem</div></td></tr>
</table>
Quackack
https://complexityzoo.net/index.php?title=Complexity_Garden&diff=6737&oldid=prev
Jgrochow: /* Table of Contents */ Added isomorphism problems and algebraic problems as categories
2021-11-19T16:55:56Z
<p><span dir="auto"><span class="autocomment">Table of Contents: </span> Added isomorphism problems and algebraic problems as categories</span></p>
<table class="diff diff-contentalign-left diff-editfont-monospace" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="en">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 16:55, 19 November 2021</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l30" >Line 30:</td>
<td colspan="2" class="diff-lineno">Line 30:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>[[#ksat|k-SAT]] -</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>[[#ksat|k-SAT]] -</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>[[#unique-ksat|Unique <math>k</math>-SAT]]</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>[[#unique-ksat|Unique <math>k</math>-SAT]]</div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; 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"> </td><td class='diff-marker'>+</td><td style="color: #202122; 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;">''Isomorphism problems:''</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; 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;">[[#graph_automorphism|Graph Automorphism]] -</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; 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;">[[#graph_isomorphism|Graph Isomorphism]] -</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; 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;">[[#ra|Ring Automorphism]] -</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; 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;">[[#ri|Ring Isomorphism]]</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; 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"> </td><td class='diff-marker'>+</td><td style="color: #202122; 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;">''Algebraic problems:''</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; 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;">[[#ra|Ring Automorphism]] -</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; 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;">[[#ri|Ring Isomorphism]] -</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; 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;">[[#approximate_shortest_lattice_vector|Approximate Shortest Lattice Vector]] -</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; 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;">[[#group_nonmembership|Group Nonmembership]] -</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; 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;">[[#integer_factorization|Integer Factorization]] -</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; 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;">[[#integer_factor|Integer Factor &#8804; k]] -</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; 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;">[[#integer_multiplication|Integer Multiplication]] -</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; 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;">[[#matrix_multiplication|Matrix Multiplication]] -</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; 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;">[[#permanent|Permanent]] -</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; 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;">[[#square_root|Square Root mod n]]</ins></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>''Sets and partitions:''</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>''Sets and partitions:''</div></td></tr>
<tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l35" >Line 35:</td>
<td colspan="2" class="diff-lineno">Line 53:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>''Uncategorized problems:''</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>''Uncategorized problems:''</div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; 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;">[[#boolean_matrix_multiplication|Boolean Matrix Multiplication]] -</ins></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>[[#3sum|3SUM]] -</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>[[#3sum|3SUM]] -</div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del style="font-weight: bold; text-decoration: none;">[[#approximate_shortest_lattice_vector|Approximate Shortest Lattice Vector]] -</del></div></td><td colspan="2"> </td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>[[#boolean_convolution|Boolean Convolution]] -</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>[[#boolean_convolution|Boolean Convolution]] -</div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del style="font-weight: bold; text-decoration: none;">[[#boolean_matrix_multiplication|Boolean Matrix Multiplication]] -</del></div></td><td colspan="2"> </td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>[[#boolean_sorting|Boolean Sorting]] -</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>[[#boolean_sorting|Boolean Sorting]] -</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>[[#discrete_logarithm|Discrete Logarithm]] -</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>[[#discrete_logarithm|Discrete Logarithm]] -</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>[[#equality|Equality]] - </div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>[[#equality|Equality]] - </div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del style="font-weight: bold; text-decoration: none;">[[#group_nonmembership|Group Nonmembership]] -</del></div></td><td colspan="2"> </td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del style="font-weight: bold; text-decoration: none;">[[#integer_factorization|Integer Factorization]] -</del></div></td><td colspan="2"> </td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del style="font-weight: bold; text-decoration: none;">[[#integer_factor|Integer Factor &#8804; k]] -</del></div></td><td colspan="2"> </td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del style="font-weight: bold; text-decoration: none;">[[#integer_multiplication|Integer Multiplication]] -</del></div></td><td colspan="2"> </td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>[[#k-local-ham|k-Local Hamiltonians]] -</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>[[#k-local-ham|k-Local Hamiltonians]] -</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>[[#k-round_sorting|k-Round Sorting]] -</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>[[#k-round_sorting|k-Round Sorting]] -</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>[[#linear_programming|Linear Programming]] -</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>[[#linear_programming|Linear Programming]] -</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>[[#majority|Majority]] -</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>[[#majority|Majority]] -</div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del style="font-weight: bold; text-decoration: none;">[[#matrix_multiplication|Matrix Multiplication]] -</del></div></td><td colspan="2"> </td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>[[#parity|Parity]] -</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>[[#parity|Parity]] -</div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del style="font-weight: bold; text-decoration: none;">[[#permanent|Permanent]] -</del></div></td><td colspan="2"> </td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del style="font-weight: bold; text-decoration: none;">[[#ra|Ring Automorphism]] -</del></div></td><td colspan="2"> </td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del style="font-weight: bold; text-decoration: none;">[[#ri|Ring Isomorphism]] -</del></div></td><td colspan="2"> </td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>[[#shortest_implicant|Short Implicant]] -</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>[[#shortest_implicant|Short Implicant]] -</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>[[#stochastic_games|Stochastic Games]] -</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>[[#stochastic_games|Stochastic Games]] -</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>[[#tautology|Tautology]] -</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>[[#tautology|Tautology]] -</div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del style="font-weight: bold; text-decoration: none;">[[#square_root|Square Root mod n]] -</del></div></td><td colspan="2"> </td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>[[#threshold(k)|Threshold(k)]]</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>[[#threshold(k)|Threshold(k)]]</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
</table>
Jgrochow
https://complexityzoo.net/index.php?title=Complexity_Garden&diff=6347&oldid=prev
Hbarnum: /* Permanent: What is a 0-1 matrix's permanent */ minor grammar fix
2015-11-07T13:58:50Z
<p><span dir="auto"><span class="autocomment">Permanent: What is a 0-1 matrix's permanent: </span> minor grammar fix</span></p>
<table class="diff diff-contentalign-left diff-editfont-monospace" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="en">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 13:58, 7 November 2015</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l394" >Line 394:</td>
<td colspan="2" class="diff-lineno">Line 394:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> |id=ra</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> |id=ra</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> |title=Ring Automorphism</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> |title=Ring Automorphism</div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div> |descript=Does a ring have non-trivial <del class="diffchange diffchange-inline">an </del>automorphism?</div></td><td class='diff-marker'>+</td><td style="color: #202122; 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> |descript=Does a ring have <ins class="diffchange diffchange-inline">a </ins>non-trivial automorphism?</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> |body=</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> |body=</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>A special case of [[#ri|Ring Isomorphism]] where the two rings investigated are the same, and where we are looking for non-trivial automorphisms.</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>A special case of [[#ri|Ring Isomorphism]] where the two rings investigated are the same, and where we are looking for non-trivial automorphisms.</div></td></tr>
</table>
Hbarnum
https://complexityzoo.net/index.php?title=Complexity_Garden&diff=6324&oldid=prev
Fgrosshans: /* #SAT: Count satisfying truth assignments */ Correct the links again : 3 CNF SAT is kSAT, and I didn't find CNF SAT here
2015-03-03T15:39:48Z
<p><span dir="auto"><span class="autocomment">#SAT: Count satisfying truth assignments: </span> Correct the links again : 3 CNF SAT is kSAT, and I didn't find CNF SAT here</span></p>
<table class="diff diff-contentalign-left diff-editfont-monospace" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="en">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 15:39, 3 March 2015</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l81" >Line 81:</td>
<td colspan="2" class="diff-lineno">Line 81:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Memberships: &#8712; [[Complexity Zoo:Symbols#sharpp|#P]]-complete</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Memberships: &#8712; [[Complexity Zoo:Symbols#sharpp|#P]]-complete</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>Related Problems: The version '''#CNF-SAT''' (counting version of [[<del class="diffchange diffchange-inline">#CNF-SAT|</del>CNF-SAT]]) and '''#3-CNF-SAT''' also called '''#3SAT''' (counting version of [[#<del class="diffchange diffchange-inline">3-CNF-SAT</del>|3-CNF-SAT]]) also are two '''#P-complete''' problems.</div></td><td class='diff-marker'>+</td><td style="color: #202122; 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>Related Problems: The version '''#CNF-SAT''' (counting version of [[CNF-SAT]]) and '''#3-CNF-SAT''' also called '''#3SAT''' (counting version of [[#<ins class="diffchange diffchange-inline">ksat</ins>|3-CNF-SAT]]) also are two '''#P-complete''' problems.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>----</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>----</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
</table>
Fgrosshans
https://complexityzoo.net/index.php?title=Complexity_Garden&diff=6323&oldid=prev
Fgrosshans: /* #SAT: Count satisfying truth assignments */ Correst red links to {{3-,}CNF-,}SAT
2015-03-03T15:35:19Z
<p><span dir="auto"><span class="autocomment">#SAT: Count satisfying truth assignments: </span> Correst red links to {{3-,}CNF-,}SAT</span></p>
<table class="diff diff-contentalign-left diff-editfont-monospace" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="en">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 15:35, 3 March 2015</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l75" >Line 75:</td>
<td colspan="2" class="diff-lineno">Line 75:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>===== <span id="sharpsat" style="color:red">#SAT</span>: Count satisfying truth assignments =====</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>===== <span id="sharpsat" style="color:red">#SAT</span>: Count satisfying truth assignments =====</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>This is the counting version of [[sat|SAT]]: given a Boolean formula, compute how many satisfying truth assignments it has. </div></td><td class='diff-marker'>+</td><td style="color: #202122; 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>This is the counting version of [[<ins class="diffchange diffchange-inline">#</ins>sat|SAT]]: given a Boolean formula, compute how many satisfying truth assignments it has. </div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Algorithms: ?</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Algorithms: ?</div></td></tr>
<tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l81" >Line 81:</td>
<td colspan="2" class="diff-lineno">Line 81:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Memberships: &#8712; [[Complexity Zoo:Symbols#sharpp|#P]]-complete</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Memberships: &#8712; [[Complexity Zoo:Symbols#sharpp|#P]]-complete</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>Related Problems: The version '''#CNF-SAT''' (counting version of [[CNF-SAT|CNF-SAT]]) and '''#3-CNF-SAT''' also called '''#3SAT''' (counting version of [[3-CNF-SAT]]) also are two '''#P-complete''' problems.</div></td><td class='diff-marker'>+</td><td style="color: #202122; 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>Related Problems: The version '''#CNF-SAT''' (counting version of [[<ins class="diffchange diffchange-inline">#</ins>CNF-SAT|CNF-SAT]]) and '''#3-CNF-SAT''' also called '''#3SAT''' (counting version of [[<ins class="diffchange diffchange-inline">#3-CNF-SAT|</ins>3-CNF-SAT]]) also are two '''#P-complete''' problems.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>----</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>----</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
</table>
Fgrosshans
https://complexityzoo.net/index.php?title=Complexity_Garden&diff=6322&oldid=prev
Fgrosshans: Correct red links Zoo → Complexity Zoo
2015-03-03T15:31:33Z
<p>Correct red links Zoo → Complexity Zoo</p>
<table class="diff diff-contentalign-left diff-editfont-monospace" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="en">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 15:31, 3 March 2015</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l108" >Line 108:</td>
<td colspan="2" class="diff-lineno">Line 108:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Algorithms: ?</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Algorithms: ?</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>Memberships: &#8712; [[Zoo#np|NP]] &#8745; [[Zoo#conp|coNP]], <math>\notin</math> [[Zoo#p|P]]?</div></td><td class='diff-marker'>+</td><td style="color: #202122; 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>Memberships: &#8712; [[<ins class="diffchange diffchange-inline">Complexity </ins>Zoo#np|NP]] &#8745; [[<ins class="diffchange diffchange-inline">Complexity </ins>Zoo#conp|coNP]], <math>\notin</math> [[<ins class="diffchange diffchange-inline">Complexity </ins>Zoo#p|P]]?</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>----</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>----</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l119" >Line 119:</td>
<td colspan="2" class="diff-lineno">Line 119:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Algorithms: ?</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Algorithms: ?</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>Memberships: &#8712; [[Zoo#fp|FP]]</div></td><td class='diff-marker'>+</td><td style="color: #202122; 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>Memberships: &#8712; [[<ins class="diffchange diffchange-inline">Complexity </ins>Zoo#fp|FP]]</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div><br>Properties: [[Zoo_Glossary#puniform|P-nonuniform?]], [[Zoo_Glossary#gap|monotone-nonmonotone gap]]</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div><br>Properties: [[Zoo_Glossary#puniform|P-nonuniform?]], [[Zoo_Glossary#gap|monotone-nonmonotone gap]]</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>----</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>----</div></td></tr>
<tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l130" >Line 130:</td>
<td colspan="2" class="diff-lineno">Line 130:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Algorithms: ?</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Algorithms: ?</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>Memberships: &#8712; [[Zoo#fp|FP]]</div></td><td class='diff-marker'>+</td><td style="color: #202122; 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>Memberships: &#8712; [[<ins class="diffchange diffchange-inline">Complexity </ins>Zoo#fp|FP]]</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div><br>Properties: [[Zoo_Glossary#puniform|P-nonuniform?]], [[Zoo_Glossary#gap|monotone-nonmonotone gap]]</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div><br>Properties: [[Zoo_Glossary#puniform|P-nonuniform?]], [[Zoo_Glossary#gap|monotone-nonmonotone gap]]</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>----</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>----</div></td></tr>
<tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l144" >Line 144:</td>
<td colspan="2" class="diff-lineno">Line 144:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Algorithms: ?</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Algorithms: ?</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>Memberships: &#8712; [[Zoo#fp|FP]]</div></td><td class='diff-marker'>+</td><td style="color: #202122; 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>Memberships: &#8712; [[<ins class="diffchange diffchange-inline">Complexity </ins>Zoo#fp|FP]]</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div><br>Properties: [[Zoo_Glossary#ospeedup|O-optimal]], symmetric, [[Zoo_Glossary#gap|monotone-nonmonotone gap]]</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div><br>Properties: [[Zoo_Glossary#ospeedup|O-optimal]], symmetric, [[Zoo_Glossary#gap|monotone-nonmonotone gap]]</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l156" >Line 156:</td>
<td colspan="2" class="diff-lineno">Line 156:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Algorithms: ?</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Algorithms: ?</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>Memberships: &#8712; [[Zoo#p|P]] </div></td><td class='diff-marker'>+</td><td style="color: #202122; 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>Memberships: &#8712; [[<ins class="diffchange diffchange-inline">Complexity </ins>Zoo#p|P]] </div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div><br>Properties: [[Zoo_Glossary#gap|monotone-nonmonotone gap]]</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div><br>Properties: [[Zoo_Glossary#gap|monotone-nonmonotone gap]]</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l204" >Line 204:</td>
<td colspan="2" class="diff-lineno">Line 204:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Algorithms: ?</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Algorithms: ?</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>Memberships: &#8712; [[Zoo#np|NP]] &#8745; [[Zoo#coam|coAM]].</div></td><td class='diff-marker'>+</td><td style="color: #202122; 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>Memberships: &#8712; [[<ins class="diffchange diffchange-inline">Complexity </ins>Zoo#np|NP]] &#8745; [[<ins class="diffchange diffchange-inline">Complexity </ins>Zoo#coam|coAM]].</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>----</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>----</div></td></tr>
<tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l218" >Line 218:</td>
<td colspan="2" class="diff-lineno">Line 218:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Algorithms: ?</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Algorithms: ?</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>Memberships: &#8712; [[Zoo#np|NP]] &#8745; [[Zoo#coam|coAM]], [[Zoo_Glossary#puniform|P-nonuniform?]]</div></td><td class='diff-marker'>+</td><td style="color: #202122; 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>Memberships: &#8712; [[<ins class="diffchange diffchange-inline">Complexity </ins>Zoo#np|NP]] &#8745; [[<ins class="diffchange diffchange-inline">Complexity </ins>Zoo#coam|coAM]], [[Zoo_Glossary#puniform|P-nonuniform?]]</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>Properties: In [[Zoo#np|NP]]\[[Zoo#p|P]] but not [[Complexity Zoo:N#npc|NP-complete]]?</div></td><td class='diff-marker'>+</td><td style="color: #202122; 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>Properties: In [[<ins class="diffchange diffchange-inline">Complexity </ins>Zoo#np|NP]]\[[<ins class="diffchange diffchange-inline">Complexity </ins>Zoo#p|P]] but not [[Complexity Zoo:N#npc|NP-complete]]?</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>----</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>----</div></td></tr>
<tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l255" >Line 255:</td>
<td colspan="2" class="diff-lineno">Line 255:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Integer Factorization in ''quantum'' polynomial time.</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Integer Factorization in ''quantum'' polynomial time.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>Memberships: &#8712; [[Complexity Zoo:F#fnp|FNP]] &#8745; [[Zoo#fbqp|FBQP]]</div></td><td class='diff-marker'>+</td><td style="color: #202122; 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>Memberships: &#8712; [[Complexity Zoo:F#fnp|FNP]] &#8745; [[<ins class="diffchange diffchange-inline">Complexity </ins>Zoo#fbqp|FBQP]]</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>Properties: In [[Zoo#np|NP]]\[[Zoo#p|P]] but not [[Zoo#npc|NP]]-complete?</div></td><td class='diff-marker'>+</td><td style="color: #202122; 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>Properties: In [[<ins class="diffchange diffchange-inline">Complexity </ins>Zoo#np|NP]]\[[<ins class="diffchange diffchange-inline">Complexity </ins>Zoo#p|P]] but not [[<ins class="diffchange diffchange-inline">Complexity </ins>Zoo#npc|NP]]-complete?</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>----</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>----</div></td></tr>
<tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l267" >Line 267:</td>
<td colspan="2" class="diff-lineno">Line 267:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Algorithms: The fastest algorithm is either the number field sieve or Lenstra's elliptic curve method, depending on the relative size of n and k. Lenstra's algorithm has heuristic randomized time complexity <math>\mathrm{poly}(n)2^{O(\sqrt{k(\log k))})}</math> if n and k have n and k digits, respectively.</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Algorithms: The fastest algorithm is either the number field sieve or Lenstra's elliptic curve method, depending on the relative size of n and k. Lenstra's algorithm has heuristic randomized time complexity <math>\mathrm{poly}(n)2^{O(\sqrt{k(\log k))})}</math> if n and k have n and k digits, respectively.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>Memberships: &#8712; [[Zoo#np|NP]] &#8745; [[Zoo#conp|coNP]]</div></td><td class='diff-marker'>+</td><td style="color: #202122; 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>Memberships: &#8712; [[<ins class="diffchange diffchange-inline">Complexity </ins>Zoo#np|NP]] &#8745; [[<ins class="diffchange diffchange-inline">Complexity </ins>Zoo#conp|coNP]]</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>----</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>----</div></td></tr>
<tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l277" >Line 277:</td>
<td colspan="2" class="diff-lineno">Line 277:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Algorithms: ?</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Algorithms: ?</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>Memberships: &#8712; [[Zoo#fp|FP]] </div></td><td class='diff-marker'>+</td><td style="color: #202122; 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>Memberships: &#8712; [[<ins class="diffchange diffchange-inline">Complexity </ins>Zoo#fp|FP]] </div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div><br>Properties: [[Zoo_Glossary#puniform|P-nonuniform?]] </div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div><br>Properties: [[Zoo_Glossary#puniform|P-nonuniform?]] </div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l316" >Line 316:</td>
<td colspan="2" class="diff-lineno">Line 316:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Algorithms: ?</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Algorithms: ?</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>Memberships: &#8712; [[Zoo#fp|FP]]</div></td><td class='diff-marker'>+</td><td style="color: #202122; 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>Memberships: &#8712; [[<ins class="diffchange diffchange-inline">Complexity </ins>Zoo#fp|FP]]</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>----</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>----</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l323" >Line 323:</td>
<td colspan="2" class="diff-lineno">Line 323:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Majority is a Boolean function with n input bits and 1 output bit. The output is 1 if the majority of input bits are 1. Examples: 001 &#8594; 0, 1100 &#8594; 1.</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Majority is a Boolean function with n input bits and 1 output bit. The output is 1 if the majority of input bits are 1. Examples: 001 &#8594; 0, 1100 &#8594; 1.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>Majority<math>\in</math>[[Zoo#p|P]]. Majority <math>\notin</math>[[Complexity_Zoo:R#reg|REG]]. Therefore, REG<math>\subsetneq</math>P.</div></td><td class='diff-marker'>+</td><td style="color: #202122; 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>Majority<math>\in</math>[[<ins class="diffchange diffchange-inline">Complexity </ins>Zoo#p|P]]. Majority <math>\notin</math>[[Complexity_Zoo:R#reg|REG]]. Therefore, REG<math>\subsetneq</math>P.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Algorithms: ?</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Algorithms: ?</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>Memberships: &#8712; [[Zoo#p|P]] </div></td><td class='diff-marker'>+</td><td style="color: #202122; 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>Memberships: &#8712; [[<ins class="diffchange diffchange-inline">Complexity </ins>Zoo#p|P]] </div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div><br>Properties: [[Zoo_Glossary#ospeedup|O-optimal]], symmetric.</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div><br>Properties: [[Zoo_Glossary#ospeedup|O-optimal]], symmetric.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l348" >Line 348:</td>
<td colspan="2" class="diff-lineno">Line 348:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Parity is a Boolean function with n inputs and 1 output. The output is 1 if the number of 1 inputs is odd. Examples: 001 &#8594; 1, 11011 &#8594; 0.</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Parity is a Boolean function with n inputs and 1 output. The output is 1 if the number of 1 inputs is odd. Examples: 001 &#8594; 1, 11011 &#8594; 0.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>Parity<math>\in</math>[[Zoo#p|P]]. Parity <math>\notin</math>[[Complexity_Zoo:F#fo|FO]] ([[zooref#Ajt83|[Ajt83]]] and [[zooref#FSS84|[FSS84]]]). Therefore, FO<math>\subsetneq</math>P.</div></td><td class='diff-marker'>+</td><td style="color: #202122; 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>Parity<math>\in</math>[[<ins class="diffchange diffchange-inline">Complexity </ins>Zoo#p|P]]. Parity <math>\notin</math>[[Complexity_Zoo:F#fo|FO]] ([[zooref#Ajt83|[Ajt83]]] and [[zooref#FSS84|[FSS84]]]). Therefore, FO<math>\subsetneq</math>P.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Algorithms: ?</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Algorithms: ?</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>Memberships: &#8712; [[Zoo#p|P]]</div></td><td class='diff-marker'>+</td><td style="color: #202122; 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>Memberships: &#8712; [[<ins class="diffchange diffchange-inline">Complexity </ins>Zoo#p|P]]</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div><br>Properties: [[Zoo_Glossary#ospeedup|O-optimal]], symmetric.</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div><br>Properties: [[Zoo_Glossary#ospeedup|O-optimal]], symmetric.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l362" >Line 362:</td>
<td colspan="2" class="diff-lineno">Line 362:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Perfect Matching is a Boolean function with n<sup>2</sup> inputs (an adjacency matrix) describing a bipartite graph and one output which is 1 if the graph has a perfect matching.</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Perfect Matching is a Boolean function with n<sup>2</sup> inputs (an adjacency matrix) describing a bipartite graph and one output which is 1 if the graph has a perfect matching.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>Perfect Matching reduces to Linear Programming, and is therefore in [[Zoo#p|P]], although specialized algorithms are also known.</div></td><td class='diff-marker'>+</td><td style="color: #202122; 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>Perfect Matching reduces to Linear Programming, and is therefore in [[<ins class="diffchange diffchange-inline">Complexity </ins>Zoo#p|P]], although specialized algorithms are also known.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>It has monotone circuit complexity of <math>n^{\Omega(\log n)}</math> (Razborov [[zooref#raz85b|[Raz85b]]]) but polynomial nonmonotone circuit complexity. </div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>It has monotone circuit complexity of <math>n^{\Omega(\log n)}</math> (Razborov [[zooref#raz85b|[Raz85b]]]) but polynomial nonmonotone circuit complexity. </div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>Perfect Matching is nonuniformly reducible to determinant and is in [[Zoo#rnc|RNC]] and [[zooref#mvv87|[MVV87]]], [[zooref#kuw86|[KUW86]]], but no deterministic [[Zoo#nc|NC]] algorithm is known.</div></td><td class='diff-marker'>+</td><td style="color: #202122; 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>Perfect Matching is nonuniformly reducible to determinant and is in [[<ins class="diffchange diffchange-inline">Complexity </ins>Zoo#rnc|RNC]] and [[zooref#mvv87|[MVV87]]], [[zooref#kuw86|[KUW86]]], but no deterministic [[Zoo#nc|NC]] algorithm is known.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Like [[#graph_isomorphism|Graph Isomorphism]], it is not known to be complete for a natural complexity class. There is a randomized or nonuniform log-space reduction of Perfect Matching to [[#graph_isomorphism|Graph Isomorphism]] [[zooref#tor00|[Tor00]]].</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Like [[#graph_isomorphism|Graph Isomorphism]], it is not known to be complete for a natural complexity class. There is a randomized or nonuniform log-space reduction of Perfect Matching to [[#graph_isomorphism|Graph Isomorphism]] [[zooref#tor00|[Tor00]]].</div></td></tr>
<tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l372" >Line 372:</td>
<td colspan="2" class="diff-lineno">Line 372:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Algorithms: ?</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Algorithms: ?</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>Memberships: &#8712; [[Zoo#p|P]] </div></td><td class='diff-marker'>+</td><td style="color: #202122; 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>Memberships: &#8712; [[<ins class="diffchange diffchange-inline">Complexity </ins>Zoo#p|P]] </div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div><br>Properties: [[Zoo_Glossary#gap|monotone-nonmonotone gap]], [[Zoo_Glossary#puniform|P-nonuniform?]].</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div><br>Properties: [[Zoo_Glossary#gap|monotone-nonmonotone gap]], [[Zoo_Glossary#puniform|P-nonuniform?]].</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l419" >Line 419:</td>
<td colspan="2" class="diff-lineno">Line 419:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Algorithms: ?</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Algorithms: ?</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>Memberships: &#8712; [[Zoo#pspace|PSPACE]] </div></td><td class='diff-marker'>+</td><td style="color: #202122; 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>Memberships: &#8712; [[<ins class="diffchange diffchange-inline">Complexity </ins>Zoo#pspace|PSPACE]] </div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>----</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>----</div></td></tr>
<tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l472" >Line 472:</td>
<td colspan="2" class="diff-lineno">Line 472:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Algorithms: ?</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Algorithms: ?</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>Memberships: [[Zoo#gc|GC]]-complete</div></td><td class='diff-marker'>+</td><td style="color: #202122; 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>Memberships: [[<ins class="diffchange diffchange-inline">Complexity </ins>Zoo#gc|GC]]-complete</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>----</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>----</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l481" >Line 481:</td>
<td colspan="2" class="diff-lineno">Line 481:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Algorithms: ?</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Algorithms: ?</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>Memberships: &#8712; [[Zoo#np|NP]] &#8745; [[Zoo#conp|coNP]], <math>\notin</math>[[Zoo#p|P]]'''?</div></td><td class='diff-marker'>+</td><td style="color: #202122; 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>Memberships: &#8712; [[<ins class="diffchange diffchange-inline">Complexity </ins>Zoo#np|NP]] &#8745; [[<ins class="diffchange diffchange-inline">Complexity </ins>Zoo#conp|coNP]], <math>\notin</math>[[<ins class="diffchange diffchange-inline">Complexity </ins>Zoo#p|P]]'''?</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>----</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>----</div></td></tr>
<tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l503" >Line 503:</td>
<td colspan="2" class="diff-lineno">Line 503:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Algorithms: ?</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Algorithms: ?</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>Memberships: &#8712; [[Zoo#fp|FP]] </div></td><td class='diff-marker'>+</td><td style="color: #202122; 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>Memberships: &#8712; [[<ins class="diffchange diffchange-inline">Complexity </ins>Zoo#fp|FP]] </div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Properties: Is a one-way function?</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Properties: Is a one-way function?</div></td></tr>
<tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l516" >Line 516:</td>
<td colspan="2" class="diff-lineno">Line 516:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Algorithms: ?</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Algorithms: ?</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>Memberships: &#8712; [[Zoo#p|P]] </div></td><td class='diff-marker'>+</td><td style="color: #202122; 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>Memberships: &#8712; [[<ins class="diffchange diffchange-inline">Complexity </ins>Zoo#p|P]] </div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div><br>Properties: symmetric.</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div><br>Properties: symmetric.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
</table>
Fgrosshans
https://complexityzoo.net/index.php?title=Complexity_Garden&diff=6321&oldid=prev
Fgrosshans: /* Discrete Logarithm: Reverse exponentiation */ Correct links towards FNP and FBQB
2015-03-03T15:20:27Z
<p><span dir="auto"><span class="autocomment">Discrete Logarithm: Reverse exponentiation: </span> Correct links towards FNP and FBQB</span></p>
<table class="diff diff-contentalign-left diff-editfont-monospace" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="en">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 15:20, 3 March 2015</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l181" >Line 181:</td>
<td colspan="2" class="diff-lineno">Line 181:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Algorithms: ?</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Algorithms: ?</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>Memberships: &#8712; [[<del class="diffchange diffchange-inline">Zoo</del>#fnp|FNP]] &#8745; [[<del class="diffchange diffchange-inline">Zoo</del>#fbqp|FBQP]]</div></td><td class='diff-marker'>+</td><td style="color: #202122; 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>Memberships: &#8712; [[<ins class="diffchange diffchange-inline">Complexity_Zoo:F</ins>#fnp|FNP]] &#8745; [[<ins class="diffchange diffchange-inline">Complexity_Zoo:F</ins>#fbqp|FBQP]]</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div><br>Properties: Is a one-way function?</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div><br>Properties: Is a one-way function?</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
</table>
Fgrosshans
https://complexityzoo.net/index.php?title=Complexity_Garden&diff=13&oldid=prev
Admin: 1 revision: Complexity zoo import.
2012-11-18T03:10:20Z
<p>1 revision: Complexity zoo import.</p>
<p><b>New page</b></p><div>__NOTOC__<br />
[[Category:Computational Complexity]]<br />
<br />
{{Menubox|{{CZ-Navbar}}}}<br />
<br />
<br />
Welcome to the '''Complexity Garden''', the botanical companion to the [[Complexity Zoo]]. This field guide lists rigorously defined computational problems, together with their relations to complexity classes, their best algorithmic results, and their relations to other problems. There are now 39 problems and (one can only hope) counting. The initial members either have or might have some exotic property related to [[speedup]] (such as [[Zoo_Glossary#ospeedup|O-speedup]], [[Zoo_Glossary#gap|monotone-nonmonotone gap]], or [[Zoo_Glossary#puniform|P-nonuniformity]]), or provide a canonical example of a complexity class (i.e. {{zcls|n|npc|NP-complete}}). ''However, all additions are welcome, and it is hoped that this will grow into a comprehensive collection.''<br />
<br />
'''Gardener''': Hunter Monroe (volunteers welcome)<br />
<br />
To create a new problem, click on the edit link of the problem before or after the one that you want to add and copy the format, and save. The preferred format of each problem is as follows: description of the problem, relations to complexity classes, their best algorithmic results (upper-bounds and lower-bounds e.g. see the [[#setcover|Set Cover]] problem), memberships and properties, and relations to other problems. Then, add the problem to the table of contents and increment the total number of problems. After this, you can use the side edit links to edit the individual sections. For more on using the wiki language, see our [[Simple_wiki_help | simple wiki help page]].<br />
<br />
If your problem is not on the list and you suspect that it might be an open problem you can check the [http://garden.irmacs.sfu.ca/ Open Problem Garden].<br />
<br />
==Table of Contents==<br />
''Graph theoretic problems:''<br />
[[#sharpperfect_matching|#Perfect Matching]] -<br />
[[#clique-like|Clique-Like]] -<br />
[[#graph_automorphism|Graph Automorphism]] -<br />
[[#graph_isomorphism|Graph Isomorphism]] -<br />
[[#perfect_matching|Perfect Matching]]<br />
<br />
''Satisfiability problems:''<br />
[[#sharpsat|#SAT]] -<br />
[[#sharpwsat|#WSAT]] -<br />
[[#constraint-sat|Constraint Satisfaction]] -<br />
[[#qbf|QBF]] -<br />
[[#qksat|Quantum k-SAT]] -<br />
[[#sat|SAT]] -<br />
[[#ksat|k-SAT]] -<br />
[[#unique-ksat|Unique <math>k</math>-SAT]]<br />
<br />
''Sets and partitions:''<br />
[[#setcover|Set Cover]]<br />
<br />
''Uncategorized problems:''<br />
[[#3sum|3SUM]] -<br />
[[#approximate_shortest_lattice_vector|Approximate Shortest Lattice Vector]] -<br />
[[#boolean_convolution|Boolean Convolution]] -<br />
[[#boolean_matrix_multiplication|Boolean Matrix Multiplication]] -<br />
[[#boolean_sorting|Boolean Sorting]] -<br />
[[#discrete_logarithm|Discrete Logarithm]] -<br />
[[#equality|Equality]] - <br />
[[#group_nonmembership|Group Nonmembership]] -<br />
[[#integer_factorization|Integer Factorization]] -<br />
[[#integer_factor|Integer Factor &#8804; k]] -<br />
[[#integer_multiplication|Integer Multiplication]] -<br />
[[#k-local-ham|k-Local Hamiltonians]] -<br />
[[#k-round_sorting|k-Round Sorting]] -<br />
[[#linear_programming|Linear Programming]] -<br />
[[#majority|Majority]] -<br />
[[#matrix_multiplication|Matrix Multiplication]] -<br />
[[#parity|Parity]] -<br />
[[#permanent|Permanent]] -<br />
[[#ra|Ring Automorphism]] -<br />
[[#ri|Ring Isomorphism]] -<br />
[[#shortest_implicant|Short Implicant]] -<br />
[[#stochastic_games|Stochastic Games]] -<br />
[[#tautology|Tautology]] -<br />
[[#square_root|Square Root mod n]] -<br />
[[#threshold(k)|Threshold(k)]]<br />
<br />
==The Problems==<br />
===== <span id="sharpperfect_matching" style="color:red">#Perfect Matching</span>: Count perfect matchings =====<br />
<br />
The #Perfect Matching problem is to count the number of perfect matchings in a bipartite graph. It is the counting version of [[#perfect_matching|Perfect Matching]]. <br />
<br />
Algorithms: ?<br />
<br />
Memberships: &#8712; [[Complexity Zoo:Symbols#sharpp|#P]]-complete <br />
<br />
Related Problems: #Perfect Matching is equivalent to [[#permanent|Permanent]].<br />
----<br />
<br />
===== <span id="sharpsat" style="color:red">#SAT</span>: Count satisfying truth assignments =====<br />
<br />
This is the counting version of [[sat|SAT]]: given a Boolean formula, compute how many satisfying truth assignments it has. <br />
<br />
Algorithms: ?<br />
<br />
Memberships: &#8712; [[Complexity Zoo:Symbols#sharpp|#P]]-complete<br />
<br />
Related Problems: The version '''#CNF-SAT''' (counting version of [[CNF-SAT|CNF-SAT]]) and '''#3-CNF-SAT''' also called '''#3SAT''' (counting version of [[3-CNF-SAT]]) also are two '''#P-complete''' problems.<br />
----<br />
<br />
===== <span id="sharpwsat" style="color:red">#WSAT</span>: Weighted SAT =====<br />
<br />
Given a Boolean formula, count the number of satisfying assignments of [[Zoo Glossary#hamming-weight|Hamming weight]] <math>k</math>. This is the canonical problem for {{zcls|symbols|sharpwt|#WT}}.<br />
<br />
Algorithms: ?<br />
<br />
Memberships: &#8712; {{zcls|symbols|sharpwt|#WT}}<br />
----<br />
<br />
<br />
===== <span id="3sum" style="color:red">3SUM</span>: Do there exist members of a list satisfying <math>a+b+c=0</math>? =====<br />
Given a list <math>X=\{x_i\}_{i=1}^n</math> of integers, do there exist elements <math>a,b,c\in X</math> such that <math>a+b+c=0</math>? This problem is important enough to computational geometry that there is defined a class of problems to which it is reducible: {{zcls|symbols|3sumhard|3SUM-hard}}.<br />
<br />
Algorithms: ?<br />
<br />
Memberships: ?<br />
----<br />
<br />
===== <span id="approximate_shortest_lattice_vector" style="color:red">Approximate Shortest Lattice Vector</span>: Does the shortest vector exceed kn? =====<br />
<br />
Given a lattice L in '''Z'''<sup>n</sup> and an integer n, does the shortest vector of L have (Euclidean) length at most kn?<br />
<br />
Algorithms: ?<br />
<br />
Memberships: &#8712; [[Zoo#np|NP]] &#8745; [[Zoo#conp|coNP]], <math>\notin</math> [[Zoo#p|P]]?<br />
----<br />
<br />
===== <span id="boolean_convolution" style="color:red">Boolean Convolution</span>: Convolution of two n-bit integers. =====<br />
<br />
Compute the convolution of two n-bit integers in binary notation <math>\sum_{i+j=k}x_i \cdot y_j</math>, where the multiplicands are respectively the i-1 and j-1 bits of the two integer inputs, and k is the k-1 bit of the output. It is a Boolean function with n input bits and 2n-1 output bits.<br />
<br />
It has monotone circuit complexity <math>\Omega(n^{3/2})</math> (Weiss) and nonmonotone circuit complexity <math>n\log n 2^{O(\log^* n)}</math> (Furer [[zooref#fur07|[Fur07]]]). <math>\log^*(n)</math> means iteratively taking <math>\log</math> of n until the result is less than 2. Nonmonotone circuits use the discrete Fourier transform (Wegener [[zooref#weg87|[Weg87]]]).<br />
<br />
Algorithms: ?<br />
<br />
Memberships: &#8712; [[Zoo#fp|FP]]<br />
<br>Properties: [[Zoo_Glossary#puniform|P-nonuniform?]], [[Zoo_Glossary#gap|monotone-nonmonotone gap]]<br />
----<br />
<br />
===== <span id="boolean_matrix_multiplication" style="color:red">Boolean Matrix Multiplication</span>: Monotone product of Boolean matrices =====<br />
Boolean Matrix Multiplication is a Boolean function with 2n<sup>2</sup> input bits (two nxn matrices) and n<sup>2</sup> output bits (an nxn matrix). The function is defined using the usual row-column rule, but using OR instead of binary addition.<br />
<br />
It has monotone circuit complexity of exactly <math>2n^3-n^2</math> (Pratt [[zooref#pra74|[Pra74]]]), but its nonmonotone circuit complexity is the same as matrix multiplication, presently <math>O(n^{2.376})</math> (Wegener [[zooref#weg87|[Weg87]]]).<br />
<br />
Algorithms: ?<br />
<br />
Memberships: &#8712; [[Zoo#fp|FP]]<br />
<br>Properties: [[Zoo_Glossary#puniform|P-nonuniform?]], [[Zoo_Glossary#gap|monotone-nonmonotone gap]]<br />
----<br />
<br />
===== <span id="boolean_sorting" style="color:red">Boolean Sorting</span>: Sort n input bits. =====<br />
<br />
A Boolean function with n inputs and n outputs that puts the 0s before the 1s. For example, 101 → 011 and 11000 → 00011.<br />
<br />
It has monotone circuit complexity <math>\Theta(n \log n)</math> (Lamagna and Savage [[zooref#LS74|[LS74]]]) and nonmonotone circuit complexity <math>\Theta(n)</math> (Muller and Preparata [[zooref#MP75|[MP75]]]). The nonmonotone circuits use binary rather than unary addition to count the 0 inputs.<br />
<br />
The outputs are the [[#threshold(k)|Threshold(k)]] functions in reverse order; in particular, the middle output is [[#majority|Majority]].<br />
<br />
Algorithms: ?<br />
<br />
Memberships: &#8712; [[Zoo#fp|FP]]<br />
<br>Properties: [[Zoo_Glossary#ospeedup|O-optimal]], symmetric, [[Zoo_Glossary#gap|monotone-nonmonotone gap]]<br />
<br />
----<br />
<br />
===== <span id="clique-like" style="color:red">Clique-Like</span>: Tardos' Clique-like approximation =====<br />
Clique-Like is a Boolean function with <math>n^2</math> inputs (an adjacency matrix) and one output.<br />
<br />
It has monotone circuit complexity of <math>\Omega\left(e^{cn^{1/6-o(1)}}\right)</math> (Tardos [[zooref#tar88|[Tar88]]]). By contrast it has polynomial nonmonotone circuit complexity, because it reduces to [[#linear_programming|Linear Programming]].<br />
<br />
Algorithms: ?<br />
<br />
Memberships: &#8712; [[Zoo#p|P]] <br />
<br>Properties: [[Zoo_Glossary#gap|monotone-nonmonotone gap]]<br />
<br />
----<br />
<br />
{{Garden-Problem<br />
|id=constraint-sat<br />
|title=Constraint Satisfaction Problem<br />
|descript=Generalized version of satisfiability problems<br />
|body=<br />
Given two sets of relations <math>I,T</math>, where <math>I</math> is the ''instance'' (not to be confused with an instance of CSP) and <math>T</math> is the ''template'', over the same vocabulary, where the vocabulary defines the names and arities of allowed relations, is there a mapping <math>h</math> such that for all relations <math>R(x_1, x_2, \dots, x_k)\in I</math>, <math>R\left(h(x_1, x_2, \dots, x_k)\right)\in T</math>?<br />
<br />
Algorithms: ?<br />
<br />
''Memberships:'' [[Complexity Zoo:N#npc|NP-complete]].<br />
<br />
''See Also:'' [[zooref#fv93|[FV93]]].<br />
}}<br />
<br />
===== <span id="discrete_logarithm" style="color:red">Discrete Logarithm</span>: Reverse exponentiation =====<br />
<br />
The discrete logarithm problem is to solve for x in the equation a<sup>x</sup> = b in some number-theoretic abelian group, typically either the group of units of a finite field or an elliptic curve over a finite field. Like the related [[#integer_factorization|Integer Factorization]], the fastest classical algorithm is the number field sieve, with heuristic time complexity <math>2^{O(n^{1/3}(\log n)^{2/3})}</math>. Also like [[#integer_factorization|Integer Factorization]], Shor's algorithm solves Discrete Logarithm in quantum polynomial time. In fact, Shor's algorithm solves Discrete Logarithm even in a black-box abelian group, provided that group elements have unique names.<br />
<br />
Algorithms: ?<br />
<br />
Memberships: &#8712; [[Zoo#fnp|FNP]] &#8745; [[Zoo#fbqp|FBQP]]<br />
<br>Properties: Is a one-way function?<br />
<br />
----<br />
<br />
{{Garden-Problem<br />
|id=equality<br />
|title=Equality<br />
|descript=Are two strings equal?<br />
|body=<br />
If Alice has a string <math>x\in\left\{0,1\right\}^n</math> and Bob has a string <math>y\in\left\{0,1\right\}^n</math>, define EQUALITY(''x'', ''y'') = 1 if and only if ''x'' = ''y''.<br />
<br />
Algorithms: ?<br />
<br />
Memberships: <!-- TODO: Fill in. --><br />
}}<br />
<br />
===== <span id="graph_automorphism" style="color:red">Graph Automorphism</span>: Is there a nontrivial automorphism? =====<br />
<br />
Graph Automorphism is equivalent to [[#graph_isomorphism|Graph Isomorphism]] in the case where the two graphs are identical.<br />
<br />
Algorithms: ?<br />
<br />
Memberships: &#8712; [[Zoo#np|NP]] &#8745; [[Zoo#coam|coAM]].<br />
<br />
----<br />
<br />
===== <span id="graph_isomorphism" style="color:red">Graph Isomorphism</span>: Are two graphs isomorphic? =====<br />
<br />
Given two graphs, are they isomorphic, i.e., is there a bijection between their vertices which preserves edges? <br />
<br />
Luks showed that Graph Isomorphism for bounded-valence graphs is in P non-uniformly (the exponent of algorithm's running time depends on the bound). Combining Luks' algorithm with a trick due to Zemlyachenko yields a time complexity upper bound of <math>2^{O(\sqrt{v \log v})}</math> for graphs with v vertices. However, some practical Graph Isomorphism algorithms, such as NAUTY, seem to run much faster than this rigorous upper bound.<br />
<br />
Like [[#perfect_matching|Perfect Matching]], it is not known to be complete for a natural complexity class.<br />
<br />
Algorithms: ?<br />
<br />
Memberships: &#8712; [[Zoo#np|NP]] &#8745; [[Zoo#coam|coAM]], [[Zoo_Glossary#puniform|P-nonuniform?]]<br />
<br />
Properties: In [[Zoo#np|NP]]\[[Zoo#p|P]] but not [[Complexity Zoo:N#npc|NP-complete]]?<br />
<br />
----<br />
<br />
{{Garden-Problem<br />
|id=group_nonmembership<br />
|title=Group Non-Membership<br />
|descript=Is an element of ''G'' a member of a subgroup ''H''?<br />
|body=<br />
<br />
Defined by [[zooref#wat00|[Wat00]]]. Let <math>G</math> be a group, whose elements are represented by polynomial-size strings. We're given a "black box" that correctly multiplies and inverts elements of <math>G</math>. Then given elements <math>g\in G</math> and <math>h_1,\dots,h_k\in G</math>, we can asked to find if <math>g\notin\left\langle h_1, \dots, h_k \right\rangle</math> (the subgroup generated by <math>h_1,\dots,h_k\in G</math>).<br />
<br />
Algorithms: ?<br />
<br />
''Memberships:'' [[Complexity Zoo:Q#qma|QMA]] [[zooref#wat00|[Wat00]]].<br />
}}<br />
<br />
===== <span id="" style="color:red">Hamiltonian circuit</span>: Exists one Hamiltonian circuit?=====<br />
<br />
Given a Graph <math>G</math>, '''exists one Hamiltonian circuit''' in <math>G</math>?<br />
<br />
Algorithms: ?<br />
<br />
''Memberships:'' [[Complexity Zoo:N#npc|NP-complete]]<br />
<br />
----<br />
<br />
===== <span id="integer_factorization" style="color:red">Integer Factorization</span>: Find an integer's prime factors =====<br />
<br />
<br />
Algorithms: The fastest known algorithm for integer factorization is the number field sieve. It has heuristic randomized time complexity <math>2^{O(n^{1/3}(\log n)^{2/3})}</math> for inputs with n digits.<br />
<br />
On the other hand, Shor's algorithm famously solves<br />
Integer Factorization in ''quantum'' polynomial time.<br />
<br />
Memberships: &#8712; [[Complexity Zoo:F#fnp|FNP]] &#8745; [[Zoo#fbqp|FBQP]]<br />
<br />
Properties: In [[Zoo#np|NP]]\[[Zoo#p|P]] but not [[Zoo#npc|NP]]-complete?<br />
<br />
----<br />
<br />
===== <span id="integer_factor" style="color:red">Integer Factor &#8804; k </span>: Is there a factor &#8804; k? =====<br />
<br />
With an upper bound on the desired prime factor, this problem is subtly different from Integer Factorization.<br />
<br />
Algorithms: The fastest algorithm is either the number field sieve or Lenstra's elliptic curve method, depending on the relative size of n and k. Lenstra's algorithm has heuristic randomized time complexity <math>\mathrm{poly}(n)2^{O(\sqrt{k(\log k))})}</math> if n and k have n and k digits, respectively.<br />
<br />
Memberships: &#8712; [[Zoo#np|NP]] &#8745; [[Zoo#conp|coNP]]<br />
<br />
----<br />
<br />
===== <span id="integer_multiplication" style="color:red">Integer Multiplication</span>: Product of two n-bit integers =====<br />
<br />
Integer Multiplication has an [[Zoo_Glossary#ospeedup|O-optimal]] linear-time algorithm on a RAM or SMM, but is thought to have [[Zoo_Glossary#ospeedup|O-speedup]] on Turing machines or [[Zoo_Glossary#puniform|P-uniform]] Boolean circuits.<br />
<br />
Algorithms: ?<br />
<br />
Memberships: &#8712; [[Zoo#fp|FP]] <br />
<br>Properties: [[Zoo_Glossary#puniform|P-nonuniform?]] <br />
<br />
----<br />
<br />
{{Garden-Problem<br />
|id=k-local-ham<br />
|title=k-Local Hamiltonians<br />
|descript=Find the smallest eigenvalue of ''m'' ''k''-local Hamiltonians acting on ''n'' qubits.<br />
|body=<br />
Given an ''n''-qubit Hilbert space, as well as a collection H<sub>1</sub>,...,H<sub>''m''</sub> of Hamiltonians (i.e. Hermitian positive semidefinite matrices), each of which acts on at most ''k'' qubits of the space. Also given real numbers ''a'',''b'' such that <math>b-a \in \Theta(1/\mathsf{poly}(n))</math>. Decide whether the smallest eigenvalue of <math>H=\sum_{i=1}^m H_i</math> is less than ''a'' or greater than ''b'', promised that one of these is the case.<br />
<br />
Algorithms: ?<br />
<br />
Memberships: ?<br />
<br />
''Properties:''<br />
* [[Complexity Zoo:Q#qma|QMA]]-complete for ''k'' = 5 [[Zooref#ksv02|[KSV02]]].<br />
* [[Complexity Zoo:Q#qma|QMA]]-complete for ''k'' = 3 [[Zooref#kr03|[KR03]]].<br />
* [[Complexity Zoo:Q#qma|QMA]]-complete for ''k'' = 2, under the assumption that [[Complexity Zoo:P#p|P]]&ne;[[Complexity Zoo:Q#q|QMA]] [[Zooref#kkr04|[KKR04]]].<br />
}}<br />
<br />
===== <span id="k-round_sorting" style="color:red">k-Round Sorting</span>: Sort inputs in &#8804; k rounds =====<br />
<br />
There are k-round sorting networks not known to be constructible in deterministic polynomial time which outperform the best-known networks constructible in deterministic polynomial time [[zooref#GGK03|[GGK03]]].<br />
<br />
Algorithms: ?<br />
<br />
Memberships: ?<br />
<br />
Properties: [[Zoo_Glossary#puniform|P-nonuniform?]]<br />
----<br />
<br />
===== <span id="linear_programming" style="color:red">Linear Programming</span>: Maximize a linear function with linear constraints =====<br />
<br />
The Linear Programming problem is to maximize a linear function in a convex polytope. It was famously shown to be in FP by Leonid Khachiyan by means of the ellipsoid method. The main algorithms used in practice are simplex and interior-point methods.<br />
<br />
Algorithms: ?<br />
<br />
Memberships: &#8712; [[Zoo#fp|FP]]<br />
----<br />
<br />
===== <span id="majority" style="color:red">Majority</span>: Are most inputs 1? =====<br />
<br />
Majority is a Boolean function with n input bits and 1 output bit. The output is 1 if the majority of input bits are 1. Examples: 001 &#8594; 0, 1100 &#8594; 1.<br />
<br />
Majority<math>\in</math>[[Zoo#p|P]]. Majority <math>\notin</math>[[Complexity_Zoo:R#reg|REG]]. Therefore, REG<math>\subsetneq</math>P.<br />
<br />
Algorithms: ?<br />
<br />
Memberships: &#8712; [[Zoo#p|P]] <br />
<br>Properties: [[Zoo_Glossary#ospeedup|O-optimal]], symmetric.<br />
<br />
Related Problems: See also [[#boolean_sorting|Boolean Sorting]] and the [http://www.math.ucdavis.edu/~greg/zoology/relations.html#majority Complexity Zoology] entry.<br />
----<br />
<br />
===== <span id="matrix_multiplication" style="color:red">Matrix Multiplication</span>: Multiply two <math>n\times n</math> matrices =====<br />
<br />
Multiply two dense <math>n\times n</math> matrices over a field <math>F</math>. Matrix Multiplication has [[Zoo_Glossary#ospeedup|O-speedup]] among Strassen-type bilinear algorithms [[zooref#cw82|[CW82]]]. Determining the minimal number of multiplications needed to compute a bilinear form (of which Matrix Multiplication is one) is {{zcls|n|npc|NP-complete}} ([[zooref#has90|[Has90]]]). This suggests that Matrix Multiplication is [[Zoo_Glossary#puniform|P-nonuniform]] over bilinear algorithms if {{zcls|n|np}}<math>\neq</math>{{zcls|c|conp|coNP}}.<br />
<br />
If the group-theoretic algorithms of Cohn et al can perform Matrix Multiplication in <math>O(n^2)</math>, then Matrix Multiplication has [[Zoo_Glossary#ospeedup|O-speedup]] among algorithms of the type they consider [[zooref#cksu05|[CKSU05]]]. <br />
<br />
Algorithms:<br />
<br />
Memberships: &#8712; {{zcls|f|fp}} <br />
<br>Properties: [[Zoo_Glossary#ospeedup|O-speedup?]], [[Zoo_Glossary#puniform|P-nonuniform]]? <br />
----<br />
<br />
===== <span id="parity" style="color:red">Parity</span>: Is the number of 1 inputs odd? =====<br />
Parity is a Boolean function with n inputs and 1 output. The output is 1 if the number of 1 inputs is odd. Examples: 001 &#8594; 1, 11011 &#8594; 0.<br />
<br />
Parity<math>\in</math>[[Zoo#p|P]]. Parity <math>\notin</math>[[Complexity_Zoo:F#fo|FO]] ([[zooref#Ajt83|[Ajt83]]] and [[zooref#FSS84|[FSS84]]]). Therefore, FO<math>\subsetneq</math>P.<br />
<br />
Algorithms: ?<br />
<br />
Memberships: &#8712; [[Zoo#p|P]]<br />
<br>Properties: [[Zoo_Glossary#ospeedup|O-optimal]], symmetric.<br />
<br />
Related Problems: Equals XOR. See the [http://www.math.ucdavis.edu/~greg/zoology/relations.html#parity Complexity Zoology] entry.<br />
----<br />
<br />
===== <span id="perfect_matching" style="color:red">Perfect Matching</span>: Is there a perfect matching? =====<br />
<br />
Perfect Matching is a Boolean function with n<sup>2</sup> inputs (an adjacency matrix) describing a bipartite graph and one output which is 1 if the graph has a perfect matching.<br />
<br />
Perfect Matching reduces to Linear Programming, and is therefore in [[Zoo#p|P]], although specialized algorithms are also known.<br />
<br />
It has monotone circuit complexity of <math>n^{\Omega(\log n)}</math> (Razborov [[zooref#raz85b|[Raz85b]]]) but polynomial nonmonotone circuit complexity. <br />
<br />
Perfect Matching is nonuniformly reducible to determinant and is in [[Zoo#rnc|RNC]] and [[zooref#mvv87|[MVV87]]], [[zooref#kuw86|[KUW86]]], but no deterministic [[Zoo#nc|NC]] algorithm is known.<br />
<br />
Like [[#graph_isomorphism|Graph Isomorphism]], it is not known to be complete for a natural complexity class. There is a randomized or nonuniform log-space reduction of Perfect Matching to [[#graph_isomorphism|Graph Isomorphism]] [[zooref#tor00|[Tor00]]].<br />
<br />
Algorithms: ?<br />
<br />
Memberships: &#8712; [[Zoo#p|P]] <br />
<br>Properties: [[Zoo_Glossary#gap|monotone-nonmonotone gap]], [[Zoo_Glossary#puniform|P-nonuniform?]].<br />
<br />
----<br />
<br />
===== <span id="permanent" style="color:red">Permanent</span>: What is a 0-1 matrix's permanent =====<br />
<br />
The permanent of an ''n''-by-''n'' 0-1 matrix (''a''<sub>''i,j''</sub>) is defined as<br />
<math>\sum_{\sigma}\prod_{i=1}^n a_{i,\sigma(i)}</math><br />
where &sigma; ranges over all permutations of the numbers 1, 2, ..., ''n''. The value of the permanent is equivalent to [[#sharpperfect_matching|#Perfect Matching]]<br />
<br />
Algorithms:<br />
<br />
Memberships: &#8712; [[Complexity Zoo:Symbols#sharpp|#P]] <br />
<br />
Properties: [[Complexity Zoo:Symbols#sharpp|#P]]-complete <br />
<br />
----<br />
<br />
{{Garden-Problem<br />
|id=ra<br />
|title=Ring Automorphism<br />
|descript=Does a ring have non-trivial an automorphism?<br />
|body=<br />
A special case of [[#ri|Ring Isomorphism]] where the two rings investigated are the same, and where we are looking for non-trivial automorphisms.<br />
}}<br />
<br />
{{Garden-Problem<br />
|id=ri<br />
|title=Ring Isomorphism<br />
|descript=Are two rings isomorphic?<br />
|body=<br />
Given two rings, are they isomorphic to each other? The counting version of the problem, #RI, asks how many different isomorphisms exist between the two rings.<br />
<br />
Algorithms: ?<br />
<br />
''Memberships:'' {{zcls|n|np}} &cap; {{zcls|c|coam|coAM}} {{zcite|KS05}}.<br />
}}<br />
<br />
===== <span id="qbf" style="color:red">QBF</span>: Quantified Boolean Formula =====<br />
<br />
Given a Boolean formula with universal and existential quantifiers, is it true? Quantified Boolean Formula (QBF) is the canonical PSPACE-complete problem.<br />
<br />
Note that {{zcite|Pap94}} calls this problem QSAT to emphasize its relationship to [[#sat|SAT]]. In particular, any instance of QBF can be written as <math>\exists x_1 \forall x_2 \cdots Q_n x_n \phi(x_1, x_2, \dots, x_n)</math>, where <math>\phi</math> is a Boolean formula as in SAT, and where <math>Q_n</math> is either a universal or existential qualifier, depending on whether <math>n</math> is even or odd. This characterization lends itself well as a candidate for reductions from two-player games.<br />
<br />
Algorithms: ?<br />
<br />
Memberships: &#8712; [[Zoo#pspace|PSPACE]] <br />
<br />
----<br />
<br />
{{Garden-Problem<br />
|id=qksat<br />
|title=Quantum k-SAT<br />
|descript=Quantum Analog for [[#sat|SAT]]<br />
|body=<br />
Given a set of measurements, each ''i'' of which involves no more than ''k'' qubits and accepts with probability ''P''<sub>''i''</sub>, and given the promise that either there exists a state such that the number of accepting measurements is "very large," or that for all states, the number of accepting measurements is very small. We are asked which of the two promise conditions holds.<br />
<br />
Algorithms: ?<br />
<br />
''Properties:'' [[Complexity Zoo:Q#qma|QMA]]-complete for ''k'' = 3.<!-- TODO: Cite this! --><br />
<br />
''See also:'' [http://www.scottaaronson.com/democritus/lec13.html Democritus Lecture 13].<br />
}}<br />
<br />
===== <span id="sat" style="color:red">SAT</span>: Is there a satisfying truth assignment? =====<br />
The SAT problem is to decide whether a given Boolean formula has any satisfying truth assignments. SAT is in NP, since a "yes" answer can be proved by just exhibiting a satisfying assignment.<br />
<br />
Algorithms: ?<br />
<br />
''Memberships:'' &#8712; {{zcls|n|npc|NP-complete}}<br />
----<br />
<br />
===== <span id="setcover" style="color:red">Set Cover</span>: Cover a set with some of its subsets =====<br />
Given a universe <math>\mathcal{U}</math> and a family <math>\mathcal{S}</math> of subsets of <math>\mathcal{U}</math>, a ''cover'' is a subfamily <math>\mathcal{C}\subseteq\mathcal{S}</math> of sets whose union is <math>\mathcal{U}</math>. In the set covering decision problem, the input is a pair <math>(\mathcal{U},\mathcal{S})</math> and an integer <math>k</math>; the question is whether<br />
there is a set covering of size <math>k</math> or less. In the set covering optimization problem, the input is a pair <math>(\mathcal{U},\mathcal{S})</math>, and the task is to find a set covering that uses the fewest sets.<br />
<br />
''Algorithms'': A simple greedy algorithm yields an <math>H(l)</math>-approximation (and hence, <math>(\ln(l)+1)</math>-approximation)where <math>l</math> is the size of largest subset in <math>\mathcal{S}</math> and <math>H(l)</math> is <math>l</math>th Harmonic number. <br />
<br />
Set covering cannot be approximated in polynomial time to within a factor of <br />
<math>\bigl(1-o(1)\bigr)\cdot\ln{n}</math>, unless '''NP''' has quasi-polynomial time algorithms [[zooref#fie98|[Fie98]]]. In addition, Set covering cannot be approximated in polynomial time to within a factor of <math>c\cdot\ln{n}</math>, where <math>c</math> is a constant, unless '''P'''<math>=</math>'''NP'''. The largest value of <math>c</math> is proved in [[zooref#ams06|[AMS06]]].<br />
<br />
''Memberships:'' Decision problem &#8712; {{zcls|n|npc|NP-complete}}, Optimization problem &#8712; {{zcls|n|npo|NP Optimization}}<br />
----<br />
<br />
===== <span id="ksat" style="color:red"><math>k</math>-SAT</span>: Satisfiability with clauses of length <math>k</math> ====<br />
For some natural number <math>k</math>, an instance of <math>k</math>-SAT is an instance of [[#sat|SAT]] in conjunctive normal form (CNF) where all clauses are the logical OR of <math>k</math> Boolean variables. <br />
<br />
Algorithms: ?<br />
<br />
Memberships: It is known that 2SAT is in {{zcls|p|p}} while 3SAT is in {{zcls|n|npc|NP-complete}}.<br />
}}<br />
<br />
<br />
===== <span id="shortest_implicant" style="color:red">Short Implicant</span>: Is there a short implicant? =====<br />
<br />
Given a DNF expression &#934;, is there a conjunction of at most k negated or non-negated literals that implies &#934;?<br />
<br />
Algorithms: ?<br />
<br />
Memberships: [[Zoo#gc|GC]]-complete<br />
----<br />
<br />
===== <span id="stochastic_games" style="color:red">Stochastic Games</span>: Is there a first player advantage? =====<br />
<br />
White, Black, and Nature alternate moving a token on the edges of a directed graph. Nature's moves are random. Given a graph, start and target nodes for the token, does White have a strategy which will make the token reach the target with probability &#8805; 1/2?<br />
<br />
Algorithms: ?<br />
<br />
Memberships: &#8712; [[Zoo#np|NP]] &#8745; [[Zoo#conp|coNP]], <math>\notin</math>[[Zoo#p|P]]'''?<br />
<br />
----<br />
<br />
===== <span id="tautology" style="color:red">Tautology</span>: Are all truth assignments satisfying? =====<br />
<br />
Tautology is {{zcls|c|conp|coNP}}-complete. <br />
<br />
Algorithms: ?<br />
<br />
''Memberships:'' &#8712; {{zcls|c|conp|coNP}}<br />
<br />
''Properties:'' [[Zoo_Glossary#pspeedup|p-speedup]]? (If so then {{zcls|n|np}} <math>\neq</math> {{zcls|c|conp|coNP}})<br />
<br />
----<br />
<br />
===== <span id="square_root" style="color:red">Square Root mod n</span>: Find square roots mod n =====<br />
<br />
The Square Root mod n problem is to solve for x in the equation x<sup>2</sup> = a mod N. Rabin noted that [[#integer_factorization|Integer Factorization]] BPP-reduces to Square Root mod n and vice-versa; the problems are equivalent.<br />
<br />
Algorithms: ?<br />
<br />
Memberships: &#8712; [[Zoo#fp|FP]] <br />
<br />
Properties: Is a one-way function?<br />
<br />
----<br />
<br />
===== <span id="threshold(k)" style="color:red">Threshold(k)</span>: Are &#8805; k inputs 1?=====<br />
Threshold(k) is a Boolean function with n input bits and one output bit.<br />
<br />
[[#boolean_sorting|Boolean Sorting]] is equivalent to the n Threshold(k) functions in reverse order. [[#majority|Majority]] is equivalent to Threshold(<math>\lceil n/2\rceil</math>).<br />
<br />
Algorithms: ?<br />
<br />
Memberships: &#8712; [[Zoo#p|P]] <br />
<br>Properties: symmetric.<br />
<br />
----<br />
<br />
===== <span id="unique-ksat" style="color:red">Unique ''k''-SAT</span>: [[#ksat|''k''-SAT]] with uniqueness promise. =====<br />
<br />
The Unique <math>k</math>-SAT problem is a [[Zoo Glossary#promise-problem|promise problem]] variant of [[#ksat|<math>k</math>-SAT]], where the promise is that each instance has either no satisfying assignment, or has exactly one satisfying assignment.<br />
<br />
Intuitively, adding this promise restricts us to only the hardest instances, as the more satisfying assignments there are, the easier it should be to find one. This intuition is justified by {{zcite|CIK+03}}, where it is also shown that if Unique <math>k</math>-SAT can be solved in deterministic time <math>O(2^{\epsilon n})</math> for all <math>\epsilon>0</math>, then so can <math>k</math>-SAT for all <math>k\ge 3</math>.<br />
<br />
Algorithms: ?<br />
<br />
Memberships: ?<br />
<br />
----</div>
Admin