Questions tagged [advice-and-nonuniformity]
Questions about advice and nonuniformity
38
questions
1
vote
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, ...
9
votes
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 ...
11
votes
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 ...
14
votes
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
...
0
votes
1answer
189 views
What do stronger circuit lower bounds give in terms of derandomization?
We have $EXP\not\subseteq P/poly\implies BPP\subseteq io-DTIME(2^{n^\epsilon})$ at every $\epsilon>0$.
This is essentially $DTIME(2^{O(n)})\not\subseteq P/poly\implies BPP\subseteq io-DTIME(2^{n^\...
2
votes
1answer
103 views
Non-Uniform Lower Bounds for NSPACE
If I'm not mistaken it is not known whether $E^{NP} \subseteq {\rm SIZE}(n)$
where $E^{NP}$ is the class of problems solvable by a TM which works in time $2^{O(n)}$ and is allowed to make queries of ...
2
votes
0answers
107 views
Complexity of $FP^{NP[O(n)]}$ with advice string?
$FP^{NP[O(n)]}$ is the functional complexity class with $O(n)$ queries to an $NP$ oracle.
Are there any interesting classes $\mathcal C$ such that
$$FP^{NP[O(n)]}\subseteq\mathcal C/\log$$
besides $...
3
votes
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 "...
9
votes
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$ ...
5
votes
1answer
265 views
Smallest $f(n)$ such that $P/f(n) = BPP/f(n)$?
It is well-known that $\mathsf{P/poly}(n) = \mathsf{BPP/poly}(n)$.
It is a major open problem to prove the conjecture $\mathsf{P} = \mathsf{BPP}$.
$\mathsf{P} = \mathsf{BPP}$ implies $\mathsf{P}/f(n) ...
12
votes
1answer
726 views
Does P/poly $\neq$ NP/poly have any interesting implications?
$P/poly = NP/poly$ implies $NP \subseteq P/poly$, which in turn has interesting consequences like the collapse of the polynomial hierarchy.
Are there interesting implications for $P/poly \neq NP/poly$...
3
votes
0answers
105 views
What is the strongest known lower bound against SIZE(n)?
What is the best known lower bound against (nonuniform) circuits of size $O(n)$? I understand that we don't know of any explicit functions that need circuits of size more than something like $5n$. But ...
17
votes
0answers
443 views
What if an $\mathsf L$-complete problem has $\mathsf{NC}^1$ circuits? More generally, what evidence is there against $\mathsf{NC}^1=\mathsf{L}$?
Edit: let me reformulate the question in a more specific way (and change the title accordingly). A slightly edited version of the original question follows.
Is there a result comparable to the Karp-...
0
votes
0answers
167 views
ExpSpace problems whose configuration reachability problems are in P/poly?
Is anything known about ExpSpace problems whose configuration reachability problems are in P/poly?
Let $M$ be an ExpSpace machine.
Given two configurations $a$ and $b$ of $M$ (of max length), ...
0
votes
1answer
139 views
Assume that $\mathsf{NP} \subseteq \mathsf{P}/\text{log(n)}$, does it imply that $\mathsf{P} = \mathsf{NP}$? [closed]
I am trying to either prove or refute the claim mentioned in the title.
Any ideas ?
8
votes
0answers
156 views
Is nonuniform $\mathsf{TC^0}$ equal to the composition closure of $\mathsf{AC^0}$ and Majority?
D.A.M. Barrington, N. Immerman and H. Straubing show in their 1990 paper
"On Uniformity Within $\mathsf{NC^1}$" that
the uniform $\mathsf{TC^0}$ is equal to $\mathsf{FOM}$
($\mathsf{FO}$ plus ...
2
votes
0answers
109 views
Conditional Results on Bounded Depth Circuit Hierarchy
$\mathsf{AC,ACC,TC}$-hierarchy are basic bounded depth circuit hierarchies.
$AC$-hierarchy is $\bigcup _{i =0}^{\infty} AC^{i} $ , where $AC^{i}$ is the $i$-th level of the hierarchy: a family of $\...
1
vote
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 ...
5
votes
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 ...
17
votes
0answers
320 views
$\mathsf{P} \ne \mathsf{P/poly} \cap \mathsf{NP}$? [duplicate]
Assuming $\mathsf{P} \ne \mathsf{NP}$ can we show $\mathsf{P} \ne \mathsf{P/poly} \cap \mathsf{NP}$? Obviously this would be the case if $\mathsf{P} \ne \mathsf{NP}$ and $\mathsf{P/poly} \supset \...
5
votes
0answers
193 views
Non-uniform average-case complexity of NP
It is conjectured that NP-complete problems are hard not only in the worst case but also in the typical case. Formally, given a language $S \in \lbrace 0,1 \rbrace^*$ and for each $n$ a probability ...
29
votes
3answers
919 views
Is NPI contained in P/poly?
It is conjectured that $\mathsf{NP} \nsubseteq \mathsf{P}/\text{poly}$ since the converse would imply $\mathsf{PH} = \Sigma_2$. Ladner's theorem establishes that if $\mathsf{P} \ne \mathsf{NP}$ then $\...
8
votes
0answers
122 views
Can polynomial-sized circuits use garbage?
This is a non-uniform (and simplified) version of my previous question about Cook reductions. Let $R\subseteq \{0,1\}^*\times\{0,1\}$. A function $r\colon \{0,1\}^*\to\{0,1\}$ solves $R$ if $(x,r(x))\...
3
votes
1answer
153 views
Speed-up of universal computation by caching
A universal computer is a program that can execute any other program. It is interesting to ask whether there are "booster" computers that execute programs faster than they execute "on their own". In ...
6
votes
2answers
2k views
Complexity of the halting problem
One of the most celebrated results in computer science is that the halting problem is undecidable. However there are still notions of complexity that are applicable. Here are 3 that I have in mind:
$...
3
votes
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. ...
3
votes
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 ...
2
votes
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 ...
15
votes
0answers
332 views
Intersecting Complexity Classes with Advice
In on hiding information from an oracle, the authors (Abadi, Feigenbaum, and Kilian) wrote:
$(\mathsf{NP/poly} \cap \mathsf{co\text-NP}{/poly})$ ... is not known to be equal to $(\mathsf{NP}...
9
votes
1answer
828 views
Non-Uniform vs. Uniform Adversaries
This question arose in the context of cryptography, but below I will present it in terms of complexity theory, since people here are more acquainted with the latter. This question is related to ...
20
votes
1answer
588 views
Problems in NP but not in Average-P/poly
The Karp–Lipton Theoem states that if $\mathsf{NP} \subset \mathsf{P/poly}$, then $\mathsf{PH}$ collapses to $\mathsf{\Sigma^P_2}$. Therefore, assuming separations between $\mathsf{\Sigma^P_2}$ and $\...
9
votes
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)$ ...
5
votes
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.
...
5
votes
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?
2
votes
2answers
252 views
Nonuniform circuit families - don't have to specify for arbitrarily large, but finite, input lengths?
This is a question about nonuniform circuit families that's kind of bothering me. Let $\lbrace C_n \rbrace$ be a family of circuits for a language $L$ such that for inputs $x$ of length $n$, $C_n(x) = ...
8
votes
1answer
162 views
Separation of classes with different amounts of advice?
The time hierarchy theorem lets one show that, for example, there are problems in P that cannot be solved in time less than const*n^2 by a Turing machine. But give the Turing machine some advice and ...
2
votes
1answer
277 views
Complexity of advice language?
Let $L$ be a language in P/poly. There is then a deterministic polynomial-time Turing machine $M$ with polynomial-sized advice that decides $L$. Consider the language $A(M)$ of all advice strings ...
10
votes
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) ...
