Lower bounds on the complexity of recognizing SAT by Turing machines (Q1603493): Difference between revisions

@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / cites work @@
+A time-space tradeoff for language recognition
@@ Property / cites work: A time-space tradeoff for language recognition / rank @@
+Normal rank
@@ Property / cites work @@
+Q4234060
@@ Property / cites work: Q4234060 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3826533
@@ Property / cites work: Q3826533 / rank @@
+Normal rank
@@ Property / cites work @@
+Nondeterministic linear-time tasks may require substantially nonlinear deterministic time in the case of sublinear work space
+Normal rank
@@ Property / cites work @@
+Towards separating nondeterminism from determinism
+Normal rank
@@ Property / cites work @@
+Two time-space tradeoffs for element distinctness
@@ Property / cites work: Two time-space tradeoffs for element distinctness / rank @@
+Normal rank
@@ Property / cites work @@
+Near-Optimal Time-Space Tradeoff for Element Distinctness
+Normal rank