New answers tagged

0

We can represent an algorithm by a Boolean algebra and implement the Boolean algebra using digital gates to form a circuit in digital electronics. The time complexity of executing the algorithm is the number of gate operations the digital circuit got. This Boolean algebra can be simplified into having only 'Not' operations in the first layer by applying De ...


1

Regarding 1: yes, since $B$ is $\mathsf{NP}$-complete it must be $\mathsf{NP}$-hard, i.e., for every problem $C$ in $\mathsf{NP}$ we have $C \le_P B$. Since $A \in \mathsf{P} \subseteq \mathsf{NP}$, we can pick $C=A$. This is true regardless of whether $\mathsf{P}=\mathsf{NP}$. Notice, however, that we are using the fact that $B$ is $\mathsf{NP}$-complete. ...


Top 50 recent answers are included