# Questions tagged [advice-and-nonuniformity]

Questions about advice and nonuniformity

38 questions
Filter by
Sorted by
Tagged with
2answers
104 views

### When is a problem specified on a TM contained in non-uniform classes such as P/poly? [closed]

In this paper by Gottesman and Irani: https://arxiv.org/abs/0905.2419 , they prove NEXP-hardness of tiling an $N\times N$ grid. They do so by encoding a TM in the tiles making up the grid. However, ...
3answers
583 views

### What are examples of how non-uniformity can be useful?

I'm curious about ways in which you have seen non-uniformity be useful in computation. One way is randomness, as in $BPP \subseteq P/poly$, and another is look-up tables which are used to show that ...
1answer
207 views

### Does the space hierarchy theorem generalize to non-uniform computation?

General Question Does the space hierarchy theorem generalize to non-uniform computation? Here are a few more specific questions: Is $L/poly \subsetneq PSPACE/poly$? For all space ...
1answer
195 views

### What are the consequences of $P \subseteq L/poly$?

A language is in $L/poly$ if there exists a logspace Turing machine that decides the language with polynomial amount of advice. See here for more info: https://en.wikipedia.org/wiki/L/poly ...
1answer
189 views

0answers
273 views

### Oracle separating $coNP$ and $NP/poly$

I'd like to prove that, with respect to some adversarial oracle $O$, $coNP^O \not\subseteq NP/poly^O$. I was thinking of using $\textsf{UNSAT}$ for this and to build my oracle as follows: $O$ will "...
1answer
255 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. Question Let $R$ be a TFNP relation. ​ Can a random oracle help P/poly to break $R$ ...
1answer
265 views

0answers
135 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 ...
0answers
246 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 ...
0answers
320 views

0answers
122 views

2answers
280 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. ...
0answers
149 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 ...
1answer
235 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 ...
0answers
332 views

0answers
285 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)$ ...
1answer
268 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. ...
1answer
384 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?
2answers
252 views

1answer
336 views

### Has the derandomization of slightly non-uniform classes, e.g BPP/linear, been studied?

By BPP/linear I refer to BPP machines with linear advice, which fulfills the promise when given the "correct" advice, and the derandomization should give us, say, a P/linear or (SUBEXP/linear) ...