View Proposal #400
If this proposal belongs to you, you are authorized to update it. Use the menu on the right.
ID | 400 |
---|---|
First Name | Debasis |
Last Name | Mandal |
Institution | Iowa State University |
Speaker Category | graduate student |
Title of Talk | Separation of NP-Completeness Notions |
Abstract | Informally speaking, reductions translate instances of one problem to instances of another problem; a problem A is polynomial-time reducible to a problem B if A can be solved in polynomial-time by making queries to problem B. By varying the manner in which the queries are allowed to make, we obtain a wide spectrum of reductions. At one end of the spectrum is Cook/Turing reduction where multiple queries are allowed and the i-th query made depends on answers to previous queries. On the other end is the most restrictive reduction, Karp-Levin/many-one reduction, where each positive instance of problem A is mapped to a positive instance of problem B, and so are the negative instances. This raises the following question: For complexity class NP, is there a Turing complete language that is not many-one complete? The first result that achieves such separation, under a reasonable hypothesis, is due to Lutz and Mayordomo. We show this separation for NP, under a believable worst-case hardness hypothesis. This is a joint work with A. Pavan and Rajeswari Venugopalan. |
Subject area(s) | Complexity Theory |
Suitable for undergraduates? | Y |
Day Preference | FridayMild |
Computer Needed? | N |
Bringing a laptop? | Y |
Overhead Needed? | N |
Software requests | |
Special Needs | |
Date Submitted | 09/30/2014 |
Year | 2014 |