The advice-and-nonuniformity tag has no wiki summary.
1
vote
0answers
67 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 ...
0
votes
0answers
94 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
163 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 ...
16
votes
0answers
247 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 ...
4
votes
0answers
89 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 ...
24
votes
3answers
600 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
95 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 ...
2
votes
1answer
93 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
463 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
191 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
122 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
166 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 ...
12
votes
0answers
161 views
Intersecting Complexity Classes with Advice
In on hiding information from an oracle, the authors (Abadi, Feigenbaum, and Kilian) wrote:
(NP/poly ∩ coNP/poly) ... is not known to be equal to (NP ∩ coNP)/poly.
They highlighted that ...
9
votes
1answer
271 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 ...
19
votes
1answer
413 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
213 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
219 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
281 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
225 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
138 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
210 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
266 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) ...
