Questions about advice and nonuniformity

learn more… | top users | synonyms (1)

0
votes
0answers
119 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
96 views
7
votes
0answers
114 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
86 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
121 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
183 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
268 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
128 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 ...
26
votes
3answers
708 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
102 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
108 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
613 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
220 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
132 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
185 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 ...
13
votes
0answers
185 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
329 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
442 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
232 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
233 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
313 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
241 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
146 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
232 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
284 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) ...