Is the following Boolean formula satisfiable? and Show that NP is closed under concatenation.

0 votes
78 views
asked Jan 19 in VU Assignments by Imad Waseem

VU Assignment

Question No. 1 (10+15 =25 marks)

Q1: (Part a): Is the following Boolean formula satisfiable?

(Part b): Show that NP is closed under concatenation.

Question No. 2 (12+13 =25 marks)

Read the research paper entitled “Computing the maximum violation of a Bell inequality is an NP-problem” and answer the following questions:

1) How can maximize the bell inequality as discussed in the paper?
2) How can you analyzed the bell inequality is NP problem of Turing machine?

1 Answer

0 votes
answered Jan 22 by Arslan

Q1: (Part a): Is the following Boolean formula satisfiable?

Boolean Formula

Answer:

According to the satisfiable critera, the above mentioned Bolean formula is not satisfiable because the combination clauses given in the formula are going to contradic with each others and usage of "AND" operator make is false.

Like, it is not possible to say existing of both "A AND NOT A" at the same time but it may be "A AND NOT B".

So, it is not satisfiable.

Welcome to Ask Questions & Get Answers, where you can ask questions and receive answers from other members of the community. You know Google Answers has been retired, and is no longer accepting new questions but we are.
...