8
$\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$
5
  • $\begingroup$ "intersection emptiness" ​ = ​ "disjointness" ​ ​ ​ ​ $\endgroup$
    – user6973
    Nov 6, 2015 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$ Nov 6, 2015 at 18:48
  • 1
    $\begingroup$ Link: cstheory.stackexchange.com/questions/22493/… $\endgroup$ Nov 6, 2015 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, 2015 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$ Nov 6, 2015 at 19:49

1 Answer 1

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
  • 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$ Nov 12, 2015 at 15:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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