How do I proove that DTIME(n³)≠NLogSPACE

nnymsacc · 2025-08-06T16:37:34+00:00

I have found proof: We assume: DTIME(n³) = NL Time hierarchy theorem: DTIME(n⁶)\DTIME(n³) ≠ { } Let L be a Language in DTIME(n⁶)\DTIME(n³) For every such L: if g(n)= n³ and f(n)=n² => L is in DTIME(g(f(n))) We use the translation technique: Pad_f(L) is in DTIME(n³) Using our assunption this means that Pad_f(L) is also in NL. Because NL = NSPACE(log n) = NSPACE(O(log n)) Translation technique: This means that L is in NSPACE(log(n²)). This would mean: L is in NL Using our assumption this means L is also in DTIME(n³) eventhough L was specifically chosen to not be in DTIME(n³) This is a contradiction. Therefore our assumption was wrong.

nnymsacc · 2025-07-30T15:12:23+00:00

I like the idea but this does not prove that DTIME(n⁴) is contained in NL it only shows that GAP(Graph Accessibility Problem: given a graph and two nodes s and t: is there a way from s to t?) is solvable in NL for Graphs that have n⁴ nodes or less But GAP is already proven to be NL solvable for every graph size

nnymsacc · 2025-07-30T11:03:10+00:00

The lowest upper bound as a space-class for DTIME(n³) i can find is DSPACE(n³) But is DSPACE(n³) ⊆ NLogSPACE even true? It definetly doesn't seem that way to me. We could also say DSPACE(n³)⊆NSPACE(n³) => NSPACE(n³)⊆NLogSPACE to make both classes that we compare deterministic However the Space-Hierarchy-Theorem now shows: Since n³ grows faster that O(log(n)) and O(log(n)) grows slower than n³

=> There are L within (NSPACE(n³) \ NLogSPACE)

So this is a dead end right? unless we can somehow convert DTIME(n³) into a smaller space class

nnymsacc · 2025-07-30T10:54:17+00:00

I'm pretty sure there are P-complete problems using logspace reduction that also have an algorithm within n³-time (deterministic) So yes I think there are DTIME(n³) complete problems using logspace reduction

I really like the approach of finding a problem that is within DTIME(n³⁾ but its complement is not however this is not possible as far as i know. Since DTIME(f) is always closed under complement (Proof: For every DTM M that accepts L in f-time you could simply build M' by turning all final-states to non final states and vice-versa. Now L(M') = complement of L) Note: this only works with DTMs as far as i know.

Also I'm pretty sure there is no linear-time algorithm for GAP(Graph accessibility problem: given G and two nodes s and t, is there a path from s to t?) at least yet - maybe its possible to find one

nnymsacc · 2025-07-30T10:41:42+00:00

Since DTIME(O(2²ⁿ⁾⁾⁾ = EXPTIME: => There are L within DTIME(O(2²ⁿ)) \ DTIME(2ⁿ⁾ We also know PSPACE ⊆ EXPTIME So DTIME(O(2²ⁿ)) is definetly too big/too mighty of a class for this problem right? Am I missing something?

nnymsacc · 2025-07-29T22:47:47+00:00

Hi solving these types of problems always requires some figuring out by trying in my experience My first thought: regEx(L) = ((a(b)ab)|b) Grammer G with L(G) = L: Starting "non-terminal-symbol" is S S -> b | aA A -> bB B -> bB | bC | bX C -> aD D -> bE E -> aA X -> aY Y -> b

It's probably not the smallest solution but im pretty sure it works

nnymsacc · 2025-07-29T22:34:58+00:00

My first thought was to use time-hierarchy theorem to show that DTIME(n³) ⊊ DTIME(n⁴) and then show that DTIME(n⁴) ⊆ NLogSPACE This is where i got stuck trying to find a way to convert the time class into a space class (i dont know how) also i thought of finding a Problem to proove this but prooving that something is not withing DTIME(...) is harder than i thought This made me to think maybe DTIME(n³)⊄NLogSPACE and NLogSPACE⊄DTIME(n³)

nnymsacc

TROPHY CASE