1
$\begingroup$

We say that a boolean circuit is boring if it returns the same result for $>\frac34$ possible input, where we have $n$ input gates. Hence, boring circuit returns the same output ($0$ or $1$) for $>\frac34 2^n$ inputs. Prove that checking if boolean circuit is boring is NP-complete

Can you help me? I have no idea how to start. I tried to reduce $3$-SAT but no result.

$\endgroup$
  • 2
    $\begingroup$ $2^n$ input gates means $2^{2^n}$ possible inputs, so you probably mean $n$ inputs. Is this homework? In any case, I'm guessing the statement is wrong, and that this problem is PP-hard, and so probably not in NP. $\endgroup$ – Ariel Aug 26 '17 at 14:49
  • $\begingroup$ @Ariel I edited and fixed typo. No, it is not homework. I practise for my exam./ $\endgroup$ – Haskell Fun Aug 26 '17 at 14:52
  • $\begingroup$ @Ariel, in fact the best result I can see that this is in $\#P$. Or $PP$ can know any constant amount of bits? $\endgroup$ – rus9384 Aug 26 '17 at 15:41
  • $\begingroup$ @rus9384 This problem cannot be in #P, since #P is a class of functions and not decision problems. $\endgroup$ – Ariel Aug 26 '17 at 16:05
  • $\begingroup$ @Ariel, I thought that every decision problem is also functional while controversal is false. The main argument is that functional machine also can output 0 or 1. $\endgroup$ – rus9384 Aug 26 '17 at 16:07
2
$\begingroup$

Given a Boolean formula $\varphi$, let $x,y$ be two fresh variables, and consider the circuit computing the function $$ x \lor y \lor \varphi. $$ This circuit is boring iff $\varphi$ is satisfiable.

$\endgroup$
  • $\begingroup$ $\phi $ is 3CNF ? $\endgroup$ – Haskell Fun Aug 26 '17 at 15:00
  • $\begingroup$ If you want it to be. In fact it could be any formula, or really any circuit. $\endgroup$ – Yuval Filmus Aug 26 '17 at 15:00
  • $\begingroup$ How many you cirucuit has input gates ? $\endgroup$ – Haskell Fun Aug 26 '17 at 15:01
  • 2
    $\begingroup$ No, that's not true. I'll let you figure that out. For example, $x \lor y \lor z$ is satisfied by 7/8 of the assignments. $\endgroup$ – Yuval Filmus Aug 26 '17 at 15:23
  • 1
    $\begingroup$ What is a bit unsatisfactory is that this answer works for "> 3/4 2^n", and could be easily adapated for "> (k / 2^m) 2^n", but not for "> c 2^n" for other values c. $\endgroup$ – gnasher729 Aug 26 '17 at 16:54
6
$\begingroup$

The problem is PP-hard. This means that unless the polynomial hierarchy collapses to NP, then deciding whether a circuit is boring is not in NP (and consequently is not NP-complete). The collapse follows from the fact that PP is closed under complement, so $\mathsf{PP=NP}$ implies $\mathsf{NP=coNP}$. We now show that deciding whether or not a circuit is boring is PP-hard.

Suppose $L\in PP$, then there exists a probabilistic polynomial Turing machine $M$ such that $x\in L \iff \Pr\left[M(x)=L(x)\right]>\frac{2}{3}$. Now consider the machine $M'$ which tosses two coins, if both output "heads" accept, otherwise execute $M$. If $x\in L$ then $M'$ accepts $x$ with probability $\frac{1}{4}+\frac{3}{4}\Pr\left[M(x)=L(x)\right]>\frac{3}{4}$. Now, let $C_x$ be the corresponding circuit for $M'$ on input $x$ (its inputs are the coins for $M'$), then $x\mapsto C_x$ is a reduction from $L$ to your problem, since $x\in L\iff C_x \text{ is boring}$. To see why, note that if $x\in L$ then $C_x$ accepts more than $\frac{3}{4}$ of the possible inputs, and if $x\notin L$ then $C_x$ accepts $\frac{1}{4}\le t\le \frac{3}{4}$ of the possible inputs.

In fact, your problem is PP-complete. To see why this language lies in PP, Let $L$ be the language of circuits who accept more than a $\frac{3}{4}$ fraction of their input, and $L'$ be the language of circuits who reject more than a $\frac{3}{4}$ fraction of their inputs. Clearly $L,L'\in PP$, and since PP is closed under union, deciding whether a circuit is boring, i.e is in $L\cup L'$, is in PP. Note that both here and in the above we used the fact that the constant in the definition of PP can be changed to any rational number.

If we want to avoid using closure properties of PP, then an argument along the following lines should work. Consider the machine $M$, which upon given an $n$-input circuit $C$, approximates the acceptance probability of $C$ by evaluating it on different uniformly distributed random length $n$ strings. Let $\hat{p}$ denote our evaluation. If $\hat{p}\ge\frac{1}{2}$, then $M$ evaluates $C$ on a random string and accept iff $C$ accepts, otherwise $M$ accepts iff $C$ rejects. Let $E$ denote the event that $|p-\hat{p}|\le \frac{1}{4}$, where $p$ is the real acceptance probability of $C$. By evaluating $C$ on polynomially many strings, we can make sure that $\Pr\left[E\right]\ge 1-\frac{1}{2^{2n}}$. If $C$ is boring, then conditioned on $E$, $M$ obtained the right evaluation of the majority of $C$ and accepts with probability $>\frac{3}{4}$. Thus, if $C$ is boring $M$ accepts with probability $>\frac{3}{4}\left(1-\frac{1}{2^{2n}}\right)$. If $C$ isn't boring, then $C$ outputs either $0$ or $1$ with probability of at most $\frac{3}{4}-\frac{1}{2^n}$. Thus, regardless of our evaluation $\hat{p}$, $M$ accepts $C$ with probability of at most $\frac{3}{4}-\frac{1}{2^n}<\frac{3}{4}\left(1-\frac{1}{2^{2n}}\right)$, which puts our language in PP.

$\endgroup$
  • $\begingroup$ It is PP-complete as the answer states. The part about the problem being in PP was wrong, now fixed. Using the closure properties of PP here seems a little overkill, If something simpler comes up I will update. In any case, to be NP-complete the problem has to be in NP, and it probably isn't. $\endgroup$ – Ariel Aug 26 '17 at 17:45
  • $\begingroup$ It is open question if $NP\stackrel{?}{=}PP$ to be precious. $\endgroup$ – rus9384 Aug 26 '17 at 17:47
  • $\begingroup$ Yes, and the answer is believed to be $\mathsf{NP\neq PP}$, since equality would imply a collapse of the polynomial hierarchy (by Toda's theorem). $\endgroup$ – Ariel Aug 26 '17 at 17:49
  • $\begingroup$ Yuval has shown that the problem is NP-hard, even undecidable problems can be NP-hard (the halting problem for example). $\endgroup$ – Ariel Aug 26 '17 at 17:50
  • $\begingroup$ @HaskellFun, it's correct: you can reduce problem X to any harder (at least as hard) problem Y and since PP-complete problems are harder than NP-complete, reduction is correct. $\endgroup$ – rus9384 Aug 26 '17 at 17:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.