Prove that P is closed under complement

Reference no: EM131731288

CS Theory Homework Problems

1. Is L_d reducible to L_u? Prove your answer.

2. Let A, B, and C be three languages. If there is a polynomial-time reduction from A to B and a polynomial-time reduction from B to C, then is there a polynomial-time reduction from A to C?

3. How many solutions does this instance of Post's Correspondence Problem (PCP) have?

A = ab, abaaa, a

B = b, ab, aaa

4. Is PCP over a unary alphabet decidable or undecidable? Prove your answer.

5. A useless state in a Turing machine is one that is never entered during a computation on any input. Let M be a TM with no useless states. Is L(M) (a) recursive, (b) RE but not recursive, or (c) not RE? Prove your answer.

6. Prove that P is closed under complement. Explain why your proof fails to show that NP is closed under complement.

You can discuss problems with others but your answers must be in your own words. Late assignments cannot be accepted.

Reference no: EM131731288

Questions Cloud

Describe seven perspectives or principles : List and briefly (two or three sentences) describe seven perspectives/principles that you have learned about that you think would be important.

Define the physician has ordered kcl 30 meq p.o. daily : The physician has ordered KCL 30 mEq p.o. daily. The medication is supplied as 40mEq/15 ml. How many mL will you administer

Procedures allowed the cargill accountant to embezzle funds : What internal controls might have stopped Cargill accountant from embezzling $3.1 million. What procedures allowed the Cargill accountant to embezzle the funds?

Define what is prinzmetal''s angina : Describe the differences between stable and unstable angina. What is Prinzmetal's angina

Prove that P is closed under complement : COMS W3261 CS Theory Homework Problems. Prove that P is closed under complement. Explain why your proof fails to show that NP is closed under complement

How many ml of each solution do you need for final solution : You have on hand a 50% syrup solution, and a 1:200 soda solution. How many mL of each solution do you need for final solution

Determine human resource strategic direction : BSBHRM602 - describes the skills and knowledge required to develop, implement and maintain a strategic approach to managing human resources in an organisation

Research and critically explain about the behaviorism : Research and critically explain five topics : Behaviorism and Cognitivism,Constructivism,Humanism .

Factor in the uneven use of hospice services : Which of the following is not a factor in the uneven use of hospice services? Medicare coverage for hospice can extend beyond six months.

User Account

All Pages