Search Results
| Search type | Search syntax |
|---|---|
| Tags | [tag] |
| Exact | "words here" |
| Author |
user:1234 user:me (yours) |
| Score |
score:3 (3+) score:0 (none) |
| Answers |
answers:3 (3+) answers:0 (none) isaccepted:yes hasaccepted:no inquestion:1234 |
| Views | views:250 |
| Code | code:"if (foo != bar)" |
| Sections |
title:apples body:"apples oranges" |
| URL | url:"*.example.com" |
| Saves | in:saves |
| Status |
closed:yes duplicate:no migrated:no wiki:no |
| Types |
is:question is:answer |
| Exclude |
-[tag] -apples |
| For more details on advanced search visit our help page | |
Results tagged with cc.complexity-theory
Search options not deleted
user 7289
P versus NP and other resource-bounded computation.
0
votes
1
answer
113
views
Problems of similar complexity for different measures
It is a common belief that $\mathbf{P}\subsetneq\mathbf{PSPACE}$, thus (most likely) there are problems that are "harder" for time than for space. But is there a problem in $\mathbf{P}$ with a poly-sp …
- 542
8
votes
Natural NP-complete problems with "large" witnesses
I came along some quite natural NP-complete problems that seemingly require long witnesses. The problems, parameterized by integers $C$ and $D$ are as follows:
Input: A one-tape TM $M$
Question: Is t …
- 542
6
votes
Equivalent definitions of time constructibility
In the last few days I thought a lot about (fully) time-constructible functions and I will present what I found out by answering Q1 and Q3. Q2 seems too hard.
Q3:
Kobayashi in his article (the refer …
- 542
14
votes
1
answer
1k
views
Equivalent definitions of time constructibility
We say that a function $f:\mathbb{N}\rightarrow\mathbb{N}$ is time-constructible, if there exists a deterministic multi-tape Turing machine $M$ that on all inputs of length $n$ makes at most $f(n)$ st …
- 542
5
votes
0
answers
188
views
Real-time countable vs fully time-constructible
Real-time countable functions were used in time hierarchy theorem in the papers of Hartmanis and Stearns (Theorem 9, 9.1 ...) and also of Hennie and Stearns (Theorems 3, 5, 7 ...). Now it is a "standa …
- 542
3
votes
An explicit separation between time-constructibility and space-constructibility?
If all space-constructible functions are time-constructible, then $EXP-TIME=EXP-SPACE$. To prove that (and to give an example of a non-trivial space-constructible but presumably not time-constructible …
- 542