Content deleted Content added
WP:COMPUTING Tagging ! (False Positive ) ?? :(Plugin++) Added {{WikiProject Computing}}. |
m Maintain {{WPBS}} and vital articles: 1 WikiProject template. Create {{WPBS}}. Keep majority rating "Start" in {{WPBS}}. Remove 1 same rating as {{WPBS}} in {{WikiProject Computing}}. Tag: |
||
| (12 intermediate revisions by 6 users not shown) | |||
Line 1:
{{WikiProject
{{WikiProject Computing|importance=|auto=yes}}
}}
i would love to either stub this or categorise this to give it some more exposure but what is this about? *puzzled* [[User:Tyhopho|Tyhopho]] 22:09, 16 March 2006 (UTC)
This article says nothing <span style="font-size: smaller;" class="autosigned">—Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/38.115.166.174|38.115.166.174]] ([[User talk:38.115.166.174|talk]]) 21:45, 23 May 2009 (UTC)</span><!-- Template:UnsignedIP --> <!--Autosigned by SineBot-->
== The "trivial" algorithm ==
Why does this page say nothing about the well-known "trivial" algorithm which independently assigns each variable to true or false (with probability 1/2), and therefore satisfies 7/8 fraction of the clauses in expectation on any instance? That algorithm can also be easily derandomized by the textbook method of conditional expectations. Am I missing something here? [[User:Piyush Sriva|Piyush]] ([[User talk:Piyush Sriva|talk]]) 03:08, 4 September 2012 (UTC)
:Karloff and Zwick allow some of the clauses to have fewer than three variables; the trivial algorithm doesn't work in that case. —[[User:David Eppstein|David Eppstein]] ([[User talk:David Eppstein|talk]]) 03:16, 4 September 2012 (UTC)
::I think that's a fair point. Though given that Hastad's reduction (as far as I know) only needs clauses with three variables, I think we should still add what the actual motivation for this algorithm is in the article. Should I go ahead and do that? [[User:Piyush Sriva|Piyush]] ([[User talk:Piyush Sriva|talk]]) 02:22, 6 September 2012 (UTC)
:::Sure, I think that makes sense. It would probably also be a good idea to clarify the difference in assumptions between the trivial algorithm and the Karloff–Zwick one, since currently we just say "3SAT" without explanation and different authors use that to mean different things. Usually it doesn't make much difference but here I guess it does. —[[User:David Eppstein|David Eppstein]] ([[User talk:David Eppstein|talk]]) 02:44, 6 September 2012 (UTC)
::::OK, I made some changes: it'd be great if you could have a look. Also, I think there is still a slight inaccuracy in the way Hastad's result is stated (the Karloff-Zwick algorithm is optimal only if we assume RP <math>\neq</math> NP, since it is a randomized algorithm). But I am not sure if spelling this out in full detail is the right way to fix this for an encyclopedia article. [[User:Piyush Sriva|Piyush]] ([[User talk:Piyush Sriva|talk]]) 02:39, 8 September 2012 (UTC)
:::::Thanks, the changes look good to me. —[[User:David Eppstein|David Eppstein]] ([[User talk:David Eppstein|talk]]) 03:04, 8 September 2012 (UTC)
| |||