Time-space tradeoffs for satisfiability
type: Item
instance of: scholarly article
title: Time-space tradeoffs for satisfiability
zbMATH Open document ID: 0955.68052
published in: Journal of Computer and System Sciences
publication date: 2001-02-18T00:00:00Z
Mathematics Subject Classification ID: 68Q15
zbMATH DE Number: 1455738
zbMATH Keywords: satisfiability
zbMATH Keywords: branching programs
author: Lance Fortnow
MaRDI profile type: Publication
full work available at URL: jcss.1999.1671
OpenAlex ID: W2015895898
cites work: Q4252736
cites work: Multiparty protocols, pseudorandom generators for Logspace, and time- space trade-offs
cites work: Q4385519
cites work: Alternation
cites work: The complexity of theorem-proving procedures
cites work: Short propositional formulas represent nondeterministic computations
cites work: A time-space tradeoff for language recognition
cites work: Q4234060
cites work: Q4289278
cites work: Q4198056
cites work: Relativized isomorphisms of NP-complete sets
cites work: Q3826533
cites work: Nondeterministic linear-time tasks may require substantially nonlinear deterministic time in the case of sublinear work space
cites work: On the Computational Complexity of Algorithms
cites work: Two-Tape Simulation of Multitape Turing Machines
cites work: Q3862379
cites work: Towards separating nondeterminism from determinism
cites work: Two time-space tradeoffs for element distinctness
cites work: Relativized Polynomial Time Hierarchies Having Exactly K Levels
cites work: Relations Among Complexity Measures
cites work: Q3993545
cites work: On O(Tlog T) reduction from RAM computations to satisfiability
cites work: Natural proofs
cites work: Relationships between nondeterministic and deterministic tape complexities
cites work: Satisfiability Is Quasilinear Complete in NQL
cites work: Theory of Formal Systems. (AM-47)
cites work: The problem of space invariance for sequential machines
cites work: PP is as Hard as the Polynomial-Time Hierarchy
cites work: A Survey of Russian Approaches to Perebor (Brute-Force Searches) Algorithms
cites work: Q4723712
cites work: Rudimentary Predicates and Relative Computation
cites work: Near-Optimal Time-Space Tradeoff for Element Distinctness
DOI: 10.1006/JCSS.1999.1671
description: scientific article; zbMATH DE number 1455738