« first day (1993 days earlier)      last day (1636 days later) » 

ABD
ABD
12:04 AM
@ThomasKlimpel Thanks for confirming, i thought of it as the equivalent to fibonnaci sequence. What if a Depth First Search is used ? is it exponential in the number of literals or variables ?
a DFS would still be exponential, right ?
Is the exponential number of satisfying assignments, exponential because of the resulting satisfying assignments after setting arbitrarily variables from a satisfying assignment (i.e. line 27) or is it exponential in the total number of satisfying assignments without considering the arbitrarily variables (i.e. line 20) ?
arbitrary*
if it was the case that it is exponential because of line 27 it can be skipped by setting all variables (entirely) to 0 or 1, that would by O(1) ?
 
 
1 hour later…
ABD
ABD
1:22 AM
I re-read your reply and i think you refer to line (27), it can be skipped by setting the missing variables in SAT entirely (i.e. non assigned variables) to (0) or entirely to (1) ... this will remove any exponential complexity.

The remaining complexity is in lines (8 to 17), is it exponential there ? I can't identify the compelxity because i am confused what forms the input size (n) for SAT, some questions on the site say it is the number of literals, others said the number of variables and some other poeple say its the number of bits to represent the input.
 
 
4 hours later…
vzn
vzn
5:21 AM
@ABD hi suggest starting out this field by studying + implementing DPLL.
@ThomasKlimpel "back from the dead"? :)
 
 
5 hours later…
ABD
ABD
9:58 AM
@vzn i read most of the materials on the internet about SAT, DPLL and local search (including books, notes, conferences, videos and podcasts). I can confirm that it is not based on DPLL or local search (i.e. there is no random variable assignment then checking for satisfaction / contradictions to the input), there is no outside interference like in DPLL or local search (i.e. how a variable is chosen to be assigned).

So i don't see the point of studying DPLL (because its not based on it ?)

@ Thomas nevermind about DFS implementation
 
Thomas Klimpel
Thomas Klimpel
10:32 AM
@ABD I am not referring to line 27. The exponential (in the number of variables) worst case runtime of your algorithm comes from line 10, because the size of ST can be exponential (in the number of variables).
 
Thomas Klimpel
Thomas Klimpel
10:47 AM
I agree that your solution is not based on DPLL. It seems to be based on a dynamic programming approach instead. I would advice against writing: "It is based on" ... "the fact that (0 != 1)." Here is one argument why your algorithm is different from DPLL, namely that its parallel runtime is different. For DPLL, the parallel runtime is given by the number of variables, but for your approach, the parallel runtime is given by the number of clauses.
 
Thomas Klimpel
Thomas Klimpel
10:58 AM
@vzn Yes and no. I started writing answers again (cstheory.stackexchange.com/questions/41832/…), (philosophy.stackexchange.com/questions/54331/…), and (philosophy.stackexchange.com/questions/56748/…). But physics will still consume most of my time.
 
Thomas Klimpel
Thomas Klimpel
11:08 AM
As for my next planed blog post, I didn't even read (arxiv.org/abs/1204.5508) yet. And normally, reading the stuff is the easy part for me, the hard part is getting all the things I want to say written down without making the whole piece unreadable or too long.
 
 
2 hours later…
ABD
ABD
1:11 PM
I see what you mean, i will try something else. Thanks for clarifying :) @ThomasKlimpel
Appreciate it'
 
 
5 hours later…
vzn
vzn
6:40 PM
 

« first day (1993 days earlier)      last day (1636 days later) »