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 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.
25
votes
Accepted
Languages beyond enumerable
Yes, for starters there is the arithmetical hierarchy, where enumerable = $\Sigma^0_1$ and it continues $\Pi^0_1$, $\Delta^0_2$, $\Sigma^0_2$ etc.
See also the Computability Menagerie.
- 24.8k
13
votes
How did the Baker-Gill-Solovay paper come to be?
Apparently, we would have gotten at least half of the BGS result without any of the three named authors and also without any of the 4 people they credit, all we needed was Dekhtiar. 😊
The Annals of t …
- 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
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
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
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
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
2
votes
Recent trends in effective analysis
The references you mention are all monographs (Abert, Pour-El and Richards, Simpson, Weihrauch). Here are some more recent (at most 5 years old) monographs which border on computable analysis:
Kohle …
- 24.8k
3
votes
Accepted
The link and equivalence between variant definition of computation model and computational c...
The following models are probably the two most well known, and they are not equivalent at the level of computability.
BCSS
standard/Grzegorczyk (same as in Weihrauch's book)
In fact, the function
…
- 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
4
votes
Accepted
How to define the input of computable function or Turing machine over real numbers
A good place to start learning about different representations of reals and their computability- and complexity-theoretic consequences is Weihrauch's book Computable Analysis.
- 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
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
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
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