2-satisfiability has been listed as one of the
Engineering and technology good articles under the
good article criteria. If you can improve it further,
please do so. If it no longer meets these criteria, you can
reassess it. Review: October 10, 2016. ( Reviewed version). |
A fact from 2-satisfiability appeared on Wikipedia's
Main Page in the
Did you know column on 29 October 2016 (
check views). The text of the entry was as follows:
|
This article is rated GA-class on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | ||||||||||||||||||
|
The article SAT solver states:
which is clearly in direct contradiction with the intro to this page, which insists on CNF! Could someone please fix? linas ( talk) 17:36, 31 March 2008 (UTC)
The diagram uses variables v0, v1, etc. whereas the formulas use x0, x1, etc. Can the owner of the diagram please change the variables to x rather than v to improve ease of comprehension. I could change the text to v1, v2, etc. but the x's are rather more typical. Ross Fraser ( talk) 22:49, 3 August 2008 (UTC)
The following sentence in the text seems to have its conclusions reversed: "if m/n is fixed as a constant α ≠ 1, the probability of satisfiability tends to a limit as n goes to infinity: if α < 1, the limit is zero, while if α > 1, the limit is one." If α < 1 (fewer clauses than variables) the limit is 1 (almost all are satisfiable) whereas if if α > 1, the limit is zero (almost none are satisfiable". Ross Fraser ( talk) 22:50, 3 August 2008 (UTC)
Was 2SAT really not known to be in P until 1979?? I'm surprised. 69.111.192.233 ( talk) 08:39, 19 November 2010 (UTC)
Clearly this shows what the satisfying assignment would be, but it's not really clear that it solves all the original clauses. The paper linked is in a pay-access database, so I can't look up his phrasing. Can anyone help with this? Twin Bird ( talk) 20:54, 3 June 2011 (UTC)
GA toolbox |
---|
Reviewing |
Reviewer: Falcon Kirtaran ( talk · contribs) 04:52, 10 October 2016 (UTC)
GA review – see WP:WIAGA for criteria
The WikiPedia article in section "Strongly Connected Components" misrepresents Aspvall/Plass/Tarjan.
In particular, checking satisfiability and (also finding an assignment for the variables) does not require the construction of the condensed graph (which is how this Wikipedia article makes it sound.)
recommend: remove everything from "Construct the condensation ... skew-symmetric" — Preceding unsigned comment added by 2601:5C0:C100:178E:E026:A06E:3FDA:33F3 ( talk) 06:12, 31 October 2016 (UTC)
2-satisfiability has been listed as one of the
Engineering and technology good articles under the
good article criteria. If you can improve it further,
please do so. If it no longer meets these criteria, you can
reassess it. Review: October 10, 2016. ( Reviewed version). |
A fact from 2-satisfiability appeared on Wikipedia's
Main Page in the
Did you know column on 29 October 2016 (
check views). The text of the entry was as follows:
|
This article is rated GA-class on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | ||||||||||||||||||
|
The article SAT solver states:
which is clearly in direct contradiction with the intro to this page, which insists on CNF! Could someone please fix? linas ( talk) 17:36, 31 March 2008 (UTC)
The diagram uses variables v0, v1, etc. whereas the formulas use x0, x1, etc. Can the owner of the diagram please change the variables to x rather than v to improve ease of comprehension. I could change the text to v1, v2, etc. but the x's are rather more typical. Ross Fraser ( talk) 22:49, 3 August 2008 (UTC)
The following sentence in the text seems to have its conclusions reversed: "if m/n is fixed as a constant α ≠ 1, the probability of satisfiability tends to a limit as n goes to infinity: if α < 1, the limit is zero, while if α > 1, the limit is one." If α < 1 (fewer clauses than variables) the limit is 1 (almost all are satisfiable) whereas if if α > 1, the limit is zero (almost none are satisfiable". Ross Fraser ( talk) 22:50, 3 August 2008 (UTC)
Was 2SAT really not known to be in P until 1979?? I'm surprised. 69.111.192.233 ( talk) 08:39, 19 November 2010 (UTC)
Clearly this shows what the satisfying assignment would be, but it's not really clear that it solves all the original clauses. The paper linked is in a pay-access database, so I can't look up his phrasing. Can anyone help with this? Twin Bird ( talk) 20:54, 3 June 2011 (UTC)
GA toolbox |
---|
Reviewing |
Reviewer: Falcon Kirtaran ( talk · contribs) 04:52, 10 October 2016 (UTC)
GA review – see WP:WIAGA for criteria
The WikiPedia article in section "Strongly Connected Components" misrepresents Aspvall/Plass/Tarjan.
In particular, checking satisfiability and (also finding an assignment for the variables) does not require the construction of the condensed graph (which is how this Wikipedia article makes it sound.)
recommend: remove everything from "Construct the condensation ... skew-symmetric" — Preceding unsigned comment added by 2601:5C0:C100:178E:E026:A06E:3FDA:33F3 ( talk) 06:12, 31 October 2016 (UTC)