7
$\begingroup$

(re "fine grained complexity") Wehar has proved that

Two DFA intersection emptiness in $O(n^{2-\epsilon})$ time → SETH false.

does anyone see any particular key proof difficulty, challenge, implication etc in the inverse of that? ie

if two DFA intersection emptiness is $\Omega(n^2)$ then SETH is true?

this two DFA intersection emptiness problem seems like a key problem to analyze/ resolve because Wehar has also shown that solving the intersection problem for $k$ DFA's in $n^{o(k)}$ time → $NL \subsetneq P$. (are there any other known problems like that? which relate L,P,NP,ExpTime?) the problem also seems similar to an old important problem complete for ExpSpace analyzed by Meyer/ Stockmeyer, "emptiness of regular expressions with squaring."

also, what is known on the best lower space bounds on this problem? (will regard partial answers on these presumably hard questions as ok.)

$\endgroup$
  • $\begingroup$ "intersection emptiness" ​ = ​ "disjointness" ​ ​ ​ ​ $\endgroup$ – user6973 Nov 6 '15 at 17:49
  • $\begingroup$ Hi VZN, I'm flattered that you've been posting about the problem that I work on. Some of what you wrote wasn't entirely correct so I submitted edits that are under stackexchange peer review. Thank you. :) $\endgroup$ – Michael Wehar Nov 6 '15 at 18:48
  • 1
    $\begingroup$ Link: cstheory.stackexchange.com/questions/22493/… $\endgroup$ – Michael Wehar Nov 6 '15 at 18:50
  • $\begingroup$ hi @Michael am focusing on/ interested in the 2-way special case only/ in particular and (understood) you have looked at n-way case and have more general results. think it is likely the n-way question reduces simply to the 2-way question. dont think anything in the math is technically incorrect. plz feel free to elaborate in Theoretical Computer Science Chat $\endgroup$ – vzn Nov 6 '15 at 19:13
  • 2
    $\begingroup$ @vzn If you can show that solving the 2 DFA problem in $O(n^{2-\epsilon})$ time implies $NL \subsetneq P$, that would be a really nice result. Currently, I can only show that solving the $k$ DFA problem in $n^{o(k)}$ time implies $NL \subsetneq P$. $\endgroup$ – Michael Wehar Nov 6 '15 at 19:49
7
$\begingroup$

The "inverse" is almost the same as

SAT is solvable in $O(2^{(1-\epsilon)n})$ time implies the intersection problem is solvable in $O(n^{2-\epsilon})$ time.

To show this, it seems that you would need to provide a reduction from an intersection problem instance of size $n$ to a SAT instance of size $2\cdot log_2(n)$.

This kind of reduction would be very interesting because it would take an instance of one problem to a much smaller instance of another problem. As a result, this reduction would not be one-to-one. Actually, there would be exponentially many inputs that map to the same output.

If you know of any interesting reductions of this form, please provide a reference. Thank you. :)

$\endgroup$
  • 1
    $\begingroup$ It's possible that there could be a reduction that takes one intersection problem instance of size $n$ to many SAT instances of size $2 \cdot \log_2(n)$. $\endgroup$ – Michael Wehar Nov 12 '15 at 15:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.