3 deleted 8 characters in body
source | link

Hi, WeWe say that a boolean circuit is boring whenif it returntsreturns 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.

Hi, We say that boolean circuit is boring when it returnts 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.

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.

2 deleted 2 characters in body
source | link

Hi, We say that boolean circuit is boring when it returnts the same result for $>\frac34$ possible input, where we have $2^n$$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.

Hi, We say that boolean circuit is boring when it returnts the same result for $>\frac34$ possible input, where we have $2^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.

Hi, We say that boolean circuit is boring when it returnts 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.

1
source | link

Show that boring boolean circuit belongs to NP-complete class

Hi, We say that boolean circuit is boring when it returnts the same result for $>\frac34$ possible input, where we have $2^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.