Timeline for Conjecture about ASP reductions between NP-complete problems
Current License: CC BY-SA 4.0
24 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 31, 2020 at 20:56 | answer | added | Marzio De Biasi | timeline score: 2 | |
| May 30, 2020 at 14:16 | history | edited | Mohammad Al-Turkistany | CC BY-SA 4.0 |
added 289 characters in body
|
| May 30, 2020 at 14:03 | comment | added | Mohammad Al-Turkistany | @EmilJeřábek If your interested in answering the post, you can use any of the other notions of natural NP-complete problems surveyed in this paper by Allender : Allender E. (2014) Investigations Concerning the Structure of Complete Sets. In: Agrawal M., Arvind V. (eds) Perspectives in Computational Complexity. Progress in Computer Science and Applied Logic, vol 26. Birkhäuser, Cham | |
| May 30, 2020 at 12:48 | history | edited | Mohammad Al-Turkistany | CC BY-SA 4.0 |
added 5 characters in body
|
| May 30, 2020 at 12:45 | comment | added | Mohammad Al-Turkistany | @EmilJeřábek Good point. For this post, natural problems are the NP-complete problems listed in Garey and Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness. See the modified post. | |
| May 30, 2020 at 6:17 | comment | added | Emil Jeřábek | Neither of your links give a definition of natural. Without it, the thing you wrote is no “conjecture”. A conjecture is an unambiguous mathematical statement that can be, in principle, proved or disproved. Putting in weasel words like “natural” makes a mockery of it. There is no way to falsify this “conjecture” because for any proposed counterexample, you will just arbitrarily decide that it is not natural. Naturally, here is a counterconjecture: there is no natural theorem about a natural class of computational problems that only works when restricted to natural problems. | |
| May 30, 2020 at 4:02 | history | edited | Mohammad Al-Turkistany | CC BY-SA 4.0 |
added 10 characters in body
|
| May 30, 2020 at 3:39 | comment | added | Mohammad Al-Turkistany | @MarzioDeBiasi Have a look at this: cs.stackexchange.com/questions/77957 | |
| May 30, 2020 at 3:00 | history | edited | Mohammad Al-Turkistany | CC BY-SA 4.0 |
added 594 characters in body
|
| May 29, 2020 at 23:42 | comment | added | Marzio De Biasi | Let us continue this discussion in chat. | |
| May 29, 2020 at 23:40 | comment | added | Mohammad Al-Turkistany | @MarzioDeBiasi SAT with only one solution (the solution set has one element) is USAT which is US-hard and it is not known to be NP-complete under Karp reduction. The conjecture involves two NP-complete problems. | |
| May 29, 2020 at 23:32 | comment | added | Marzio De Biasi | @MohammadAl-Turkistany: ok perhaps I didn't understand the question. Suppose you have an instance of SAT with only one solution (the solution set has one element), how can you 1:1 map it to the solution set of an instance of Hamiltonian Path on cubic graphs? | |
| May 29, 2020 at 23:05 | comment | added | Mohammad Al-Turkistany | @MarzioDeBiasi NO, in BH conjecture, the bijection is between instances. | |
| May 29, 2020 at 23:03 | comment | added | Marzio De Biasi | So you mean the (unsolved) well known Berman–Hartmanis conjecture? | |
| May 29, 2020 at 23:01 | history | edited | Mohammad Al-Turkistany | CC BY-SA 4.0 |
added 200 characters in body; edited title
|
| May 29, 2020 at 22:55 | history | edited | Mohammad Al-Turkistany | CC BY-SA 4.0 |
added 200 characters in body; edited title
|
| May 29, 2020 at 22:50 | history | edited | Mohammad Al-Turkistany | CC BY-SA 4.0 |
added 200 characters in body; edited title
|
| May 29, 2020 at 22:37 | comment | added | Mohammad Al-Turkistany | @MarzioDeBiasi The conjecture is not about ASP-completeness. It is about restricting Karp reduction to a reduction that requires polynomial time computable bijection on solution sets. | |
| May 29, 2020 at 22:28 | comment | added | Marzio De Biasi | You should check the notion of ASP-completeness and NP-completeness of n-ASP (both defined in Takayuki Yato "Complexity and Completeness of Finding Another Solution and its Application to Puzzles"). Furthermore finding an Hamiltonian cycle in cubic graphs is NP-complete, but the corresponding function problem is not ASP-complete (because a cubic graph with a Hamiltonian circuit always has another); so your conjecture seems false. | |
| May 29, 2020 at 22:14 | comment | added | Mohammad Al-Turkistany | @EmilJeřábek See cstheory.stackexchange.com/questions/27215 and cstheory.stackexchange.com/questions/33076 | |
| May 29, 2020 at 19:45 | comment | added | Emil Jeřábek | Define “natural”. | |
| May 29, 2020 at 18:53 | history | edited | Mohammad Al-Turkistany | CC BY-SA 4.0 |
added 21 characters in body
|
| May 29, 2020 at 18:44 | history | edited | Mohammad Al-Turkistany | CC BY-SA 4.0 |
added 14 characters in body
|
| May 29, 2020 at 18:38 | history | asked | Mohammad Al-Turkistany | CC BY-SA 4.0 |