# Tagged Questions

232 views

### Can a random oracle change which TFNP problems are strongly hard-on-average?

I've been thinking about the following question at various times since I saw this question on Cryptography. As mentioned in my bounty message: I would accept a proof that the implication ...
118 views

125 views

### Smallest Nonuniform Complexity Classes including uniform-P

As we know, studiyng differences between uniform complexity and nonuniform complexity class is crucial. For example, P/poly is defined as challenges to derive a separation between P and NP, because ...
206 views

### Is Solomonoff Induction in $\mathsf{P/poly}$?

Consider any language $L$. Define $s(L) \in {\lbrace 0, 1 \rbrace}^\omega$ (an infinite sequence of bits) by the recursive formula $$s(L)_n=\chi_L(s(L)_{<n})$$ Here $\chi_L$ is the characteristic ...
289 views

112 views

236 views

### Separation of space complexity classes: differeces between uniform class and nonuniform one as an analogy of circuit lower bounds project

Boolean circuit is used to measure time in a nonuniform way, which Pippenger showed the relation between a time complexity of uniform model (Turing Machines) and size complexity of boolean circuits. ...
138 views

### Survey on the Power of Non-Uniformity

I know that BPP is in P/poly. I know that if NP is in P/poly then $PH = \Sigma^2_p$ Question: Is there a good survey on the power of non-uniformity? I'm basically looking for a list of known ...
206 views

### Recommendation for a good book on first order logic w.r.t inductive logic programming

I have had 10 days to read up on Computational Logic but the books I am following are only succeeding in confusing me. I find most of text's ( Niehuys-Cheng & de Wolf 1997, De Raedt 2008, Lloyd ...
293 views

249 views

### Beating Nonuniformity by Oracle Access

Informally, we say that a Turing machine $M(\cdot)$ approximates a function $f(\cdot)$ if their outputs on a series of inputs are indistinguishable. More formally, let $L$ be a language, $M(\cdot)$ ...
245 views

### The Complexity of Advice in Computational Indistinguishability

One of the cornerstones of the modern cryptography is the definition of computational indistinguishability: It is used in definition of cryptosystems, pseudorandom generators, zero-knowledge, etc. ...
362 views

### Logarithmic advice language in P?

Is something like DTIME(poly(n))/log(n) in P? Can the log-length advice be somehow hardwired into a DTM for P?