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 computational-complexity
Search options answers only
not deleted
user 4600
This is a branch that includes: computational complexity theory; complexity classes, NP-completeness and other completeness concepts; oracle analogues of complexity classes; complexity-theoretic computational models; regular languages; context-free languages; Komolgorov Complexity and so on.
10
votes
How many Complexity Classes do you know?
The top part of the Computability Zoo (r.e., recursive, and beyond) is covered in more detail in the Computability Menagerie.
- 24.8k
1
vote
Longest run of heads
[This answer is a followup to Anthony Quas' comment and your subsequent request for an explicit map.]
Let's list all the outcomes as $x_1\prec x_2\prec\dots\prec x_{2^n}$ in the following order:
$x$ …
- 24.8k
3
votes
Accepted
If the set of the output of a computable function is finite, is the sequence periodic eventu...
Regarding the 2nd question, the set of output sequences of an autonomous finite automaton consists of ultimately periodic sequences.
- 24.8k
3
votes
Is the Kolmogorov complexity of at least one string of a given length equal to its length?
It depends on the universal machine. Consider length 0, the empty string could have complexity 455, say.
- 24.8k
6
votes
powers in strings
Regarding the 3rd question, I will show this:
Theorem. For a random binary word of length $n$, the expected number of $h$th powers is
$$
\sim \frac{n}{2^{h-1}-1}.
$$
Proof. A basic event about occurr …
- 24.8k
3
votes
Accepted
The definition of computational complexity or complexity measure of computing reals
This is interesting. I think a number could be of low complexity in terms of approximating it to within smaller and smaller $\epsilon $, while of high complexity in terms of finding its binary represe …
- 24.8k
1
vote
Complete classification of complexity classes / infinite approaching sequences
Let us write $f\le_O g$ if $O(f)\le O(g)$, i.e., $f=O(g)$.
There is much to say about this order, but I'll stick to whether it looks like your suggestion:
A dictionary ordered version of some pow …
- 24.8k
6
votes
Accepted
What is the probability a random Turing machine is isomorphic to a DFA?
The set of possible answers to this question is a countable dense subset of (0,1), because it depends on your choice of universal Turing machine.
- 24.8k
3
votes
Accepted
Diagonalization and classes of computable functions
The set of polytime computable functions does indeed have a computable representative. Note that for $f$ to be polytime computable means there exists $t$, and $n_0$ such that for all $n\ge n_0$ it tak …
- 24.8k
4
votes
Connections between algebraic semantics and computational complexity of a logic?
The example you gave extends as follows:
SAT for arbitrary lattices (meaning, is a given formula satisfiable in some lattice) is polynomial-time decidable
SAT for modular lattices is Turing undecida …
- 24.8k
7
votes
Complexity of Turing Machine behavior
If you restrict attention to TMs that always halt, then:
One measure of complexity of a Turing machine is its running time, the maximum number of steps taken before it halts on inputs of length $n$, …
- 24.8k
3
votes
Computational complexity of solution of Pell equation and more
The problem of finding $x$ and $y$ in a given Pell equation $x^2-ny^2=1$ is not known to be solvable in polynomial time, see Wikipedia.
- 24.8k
1
vote
Accepted
Generating an arbitrarily long sequence with decreasing Kolmogorov complexity of terms
Suppose there is such an algorithm.
Let $x_n$ be the first string outputted on input $$s=00\cdots 0=0^n.$$
Then $x_n$ has complexity at most $\log_2 n+C$ since I just described it in terms of $n$.
On …
- 24.8k
11
votes
Can We Decide Whether Small Computer Programs Halt?
You're right that such a project is possible. Calude et al. (http://www.emis.de/journals/EM/expmath/volumes/11/11.3/Calude361_370.pdf) have some results in this direction.
- 24.8k
1
vote
Are there any continuous-time stochastic processes in which transition probabilities are dis...
One example type is a jump process that jumps at certain predetermined times, as in @AnthonyQuas' comment.
For instance, a stock price that can only make jumps when markets open, like New Zealand Sto …
- 24.8k