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 |