Believe it or not computers or more correctly processing units (PUs) are becomin

Question

Believe it or not computers or more correctly processing units (PUs) are becoming part of things we use in everyday life. For example in modern automobiles, a PU may control the braking system, and another may control fuel injection. Similarly, hundreds of PU may work together to make a plane fly. Consider a specific system SYS.SYS has n identical PUs that are connected in a communication network. It takes cooperation of exactly k PUs to perform an operation of size k. However, two Pus can cooperate only if they are directly connected in the communication network. The SYS would like to figure out the largest operation it can perform. Prove that SYS has an NP-complete problem in his bag. To help SYS you can assume that 3SAT is NP-complete.

Explanation / Answer

Communication system:

a communications system is a collection of individual communications networks, transmission systems, relay stations, tributary stations, and data terminal equipment (DTE) usually capable of interconnection and interoperation to form an integrated whole. The components of a communications systemserve a common purpose, are technically compatible, use common procedures, respond to controls, and operate in union. Telecommunications is a method of communication

So basically processing unit is to manage the each individual systems to process and the systems should follow the PU protocols to woking on their communication systems

In sys to sys communication we have buses are there to communicate them well and to tansfer the information

3SAT is NP-complete:

SAT Problem :- Given a set of clauses C1, C2, . . . , Cm in CNF form, where Ci contains literals from x1, x2, . . . , xn problem is to check if all clauses are simultaneously satisfiable. Cook-Levin theorem shows that SAT is NP-Complete. 3SAT problem ¯ :- Given a set of clauses C1, C2, . . . , Cm in 3CNF from variables x1, x2, . . . , xn problem is to check if all the clauses are simultaneously satisfiable. 3SAT := {Satisfiable 3CNF formulae } Proof Sketch:3SAT problem is in NP since any assignment of values to variables can be verified in polynomial time. We show that 3SAT is also NP-Complete by showing a reduction from SAT to 3SAT in polynomial time. SAT p 3SAT We reduce each clause of the SAT instance containing more than 3 literals into a conjunction of several new clauses in 3SAT instance as follows: 1. Create a new clause for 3SAT instance containing first two literals of corresponding SAT instance clause and OR it with a free variable say z1. 2. Make new clause in conjunction with previous clause and add the next literal of SAT instance clause and OR it with ¯z1 i.e. negation of free variable used in previous clause and OR it with a new free variable say z2. 3. Repeat step 2 with next clause in conjunction with previous clause containing next literal of original CNF clause OR with ¯z2 and further ORed with z3.Continue this process till last two literals in original SAT instance clause will be left. Last clause will contain negation of free literal of previous clause ORed with last two literals in corresponding clause in SAT instance. 4. Repeat step 1 to 3 for next SAT instance clause and keep the output in conjunction with previous 3SAT instance clauses. Hence if a particular SAT instance clause contain m literals where m > 3 then the reduced 3SAT instance will contain m 2 clauses in conjunction and contain m 3 free variables. So, this reduction is polynomial in time and space. Reduction Example:- C = x1 x¯2 x3 x¯4 x5 (x1 x¯2 z1) (x3 z¯1 z2) ( ¯x4 x5 z¯2) Claim 1 : If the SAT instance is satisfiable then so is the corresponding 3SAT instance. SAT instance is satisfiable when every clause evaluates to True simultaneously . If a clause in SAT instance is True then at least one literal in it is True. So in the corresponding reduced 3SAT instance the 3CNF clause containing that literal is True and we can make free literals ORed with this literal to zero so that its negation in its neighboring 3CNF clause evaluates to one. Keep this alteration to make all 3CNF clauses evaluate to one. Claim 2 : If 3SAT instance is satisfiable then so is SAT instance. Since each 3CNF clauses evaluates to True, so every reduced 3CNF clauses from original 3SAT instance clause evaluates to True. This can happen only if at least one original literal present in SAT instance clause is True because if all original literals have value False then only free variable can not make all 3CNF clause True since free variable are present in alternative negation in neighboring clause , so at least one clause will be False. Thus atleast one original literal is True which will make corresponding SAT instance clause True. By Claim 1 and Claim 2 we conclude that 3SAT is NP -Complete.

Related Questions

Navigate

• Browse (All)
• Browse B
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.