Arthur MILCHIOR
  • Member for 11 years, 5 months
  • Last seen more than 1 year ago
Is $(NP^{NP})^{NP} = NP^{(NP^{NP})}$?
Accepted answer
13 votes

${\Sigma_2^P}^{NP}$ is the set of language decided by an alternating turing machine in existential, and then universal state, with an oracle in NP. Both the universal and the existantial part can ...

View answer
Is $P^{\#P}=(P^{\#P})^{\#P}$ ?
Accepted answer
12 votes

You should probably take a look at Is $(NP^{NP})^{NP} = NP^{(NP^{NP})}$? and Are Oracles Associative?. I don't know any canonical definition of $(A^B)^C$ hence I've got the same problem as Tsuyoshi ...

View answer
Algorithms from the Book.
9 votes

I guess the algorithm to "hash-cons" is really interesting. This idea let us usually save both memory, time, and avoid doing many time the same computation by finding quickly equality between many ...

View answer
Algorithms from the Book.
9 votes

I think that there should be at least one persistant data structure. In particular, the "persistant array" let us obtains a lot of other persistant data-structures where we wouldn't expect them.

View answer
Algorithms from the Book.
7 votes

I would like to put some non-deterministic algorithm, which may also be in the Book. In particular, I think of the Immerman's algorithm for non-reachability in directed graph in non deterministic log ...

View answer
Regular expressions aren't
6 votes

It is known that perl's so-called regexp is powerful enough to be Turing complete; there is even a compiler from usual program to perl regexp. Hence I doubt it makes sense to search for a name for ...

View answer
Are Oracles Associative?
5 votes

As Venkat told in comments, it seems hard to understand your definition for oracle which aren't defined as some machine characterisation. Let $A^{(B^C)}$ would be the set of TM in $A$ with an oracle ...

View answer
Dinner-table description of theoretical computer science?
5 votes

Usually I give the factoring problem as example; I first ask for the number that divide 15; usually people can answer 3, 5, and have fun wondering if 1 and 15 are correct answer. Then I give a huge ...

View answer
Definition for MSO2 for arbitrary structures
5 votes

If I understand correctly, you just want a definition of the logic; then you can find a definition of MSO$_j$ (where 2 is a special case) by example in ''Elements of Finite Model Theory'' of Leonid ...

View answer
Parallel Dynamic Search
5 votes

I think you may find interesting answer in Okasaki's book Purely Functional Data Structures. In this book, many data structures are shown, such that every updates are not expensive (usually only take ...

View answer
Is there a natural restriction of VO logic which captures P or NP?
4 votes

For information, VO is in fact really more powerful than what you state; it contains the entire analytical hierarchy (hence, also the entire arithmetical hierarchy). The result is not published, ...

View answer
space-bounded TMs and oracles
3 votes

NSPACE(0)P=RE wich I guess is tad bit absurd. Indeed, let L be a language recursively enumerable, M a TM who recognise L and M′ a TM that read an input and a number n of "1" and then simulates M for ...

View answer
Is there a natural restriction of VO logic which captures P or NP?
2 votes

To answer to your comment, I guess I should make another answer, speaking only on Krom and Horn (May be I should ask a question about those to CSTheory) I suggest that you read section 5.3 page 34 of ...

View answer