Solved-Homework 5 -Solution

Description

1. An almost clique is any graph that is the result of deleting one edge from a clique. Prove that the problem of whether a graph G has an almost clique of size t is NP-complete.

2. Show 0-1-2 integer programming is NP-complete where 0-1-2 integer programming is the problem: Given a list of m linear inequalities with rational coefficients over n variables u1,…un (i.e., m inequalities of the form a1u1+a2u2+⋯+anun≤b where the ai and b are fraction pq for some integers p and q), decide if there is an assignment of the numbers 0, 1, or 2 to the variables that satisfies all the inequalities.

3. A neural net gate NN(x1,…,xn,w0,w1,…,wn) outputs 1 if w0+∑iwixi>0 and 0 otherwise. Here xi→ are viewed as the inputs and wi−→ are called weights. We imagine weights are fixed after some training process. A neural network is a directed acyclic graph where the nodes are labelled

with NN gates. The output of such a network is computed in the natural way by evaluating gates which are immediately connected to the inputs, followed by gates all whose inputs now have values, and so on. Define the neural network understanding (NNU) problem to be given a neuralnetwork N and a setting for its weights w⃗, decide if there is a setting of its inputs x⃗ which makes it output 1. Show the NNU problem is NP-complete.