Pith. sign in

REVIEW 1 cited by

Trading Determinism for Time in Space Bounded Computations

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 1606.04649 v1 pith:R56JGCJC submitted 2016-06-15 cs.CC

Vivek Anand T Kallampally , Raghunath Tewari This is my paper · ORCID
classification cs.CC
keywords spacetimealgorithmrequiresdeterministiceverymathcalnondeterministic
verification ladder T0 review T1 audit T2 compute T3 formal

Signed reviews

No signed human review yet.

0 comments
abstract

Savitch showed in $1970$ that nondeterministic logspace (NL) is contained in deterministic $\mathcal{O}(\log^2 n)$ space but his algorithm requires quasipolynomial time. The question whether we can have a deterministic algorithm for every problem in NL that requires polylogarithmic space and simultaneously runs in polynomial time was left open. In this paper we give a partial solution to this problem and show that for every language in NL there exists an unambiguous nondeterministic algorithm that requires $\mathcal{O}(\log^2 n)$ space and simultaneously runs in polynomial time.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Linear Matroid Intersection is in Catalytic Logspace

    cs.CC 2025-09 conditional novelty 7.0 of 10

    Linear matroid intersection is solvable in catalytic logspace with polynomial time, the hardest problem yet known to lie in the class CL.

Pith tools