Timeline for in SAT resolution proofs, are all DAGs possible?
Current License: CC BY-SA 3.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 17, 2013 at 23:16 | comment | added | vzn | fyi, am accepting this answer because the question was (unfairly) closed & there is no opportunity for new, complete, creative etc. answers | |
| Feb 17, 2013 at 23:15 | vote | accept | vzn | ||
| Feb 16, 2013 at 18:03 | comment | added | Shaull | Indeed, I meant in-degree. | |
| Feb 16, 2013 at 17:50 | comment | added | vzn | that should read "3 or more". "degree" is defined for undirected graphs, but what is "degree" defined as on a DAG? guess you mean "indegree"? anyway, related question, if not all 2-descendant (2-indegree) DAGs are possible (not convinced of this yet), what characterizes the resolution-based DAG class? is it considered elsewhere? etc. | |
| Feb 16, 2013 at 17:33 | comment | added | Shaull | Technically you can get any even degree, depending on whether you distinguish identical nodes formed from different clauses. | |
| Feb 16, 2013 at 17:28 | comment | added | vzn | is this a proof that there exist DAGs with more than 3 edges into a node that cant be Resolution proofs? sorry, realize, need to modify the question for that case. all resolution proofs of course are "2-descendant" DAGs | |
| Feb 16, 2013 at 17:16 | history | answered | Shaull | CC BY-SA 3.0 |