Complexity with Rod

详细信息    查看全文

• 刊名：Lecture Notes in Computer Science
• 出版年：2017
• 出版时间：2017
• 年：2017
• 卷：10010
• 期：1
• 页码：115-121
• 参考文献：1.Downey, R., Fortnow, L.: Uniformly hard languages. Theor. Comput. Sci. 298(2), 303–315 (2003)MathSciNet CrossRef MATH
  2.Fortnow, L.: Kolmogorov complexity. In: Downey, R., Hirschfeldt, D. (eds.) Aspects of Complexity, Minicourses in Algorithmics, Complexity, and Computational Algebra, NZMRI Mathematics Summer Meeting. de Gruyter Series in Logic and Its Applications, Kaikoura, New Zealand, 7–15 January 2000, vol. 4. de Gruyter (2001)
  3.Downey, R., Hirschfeldt, D.: Algorithmic Randomness and Complexity. Springer Science & Business Media, Heidelberg (2010)CrossRef MATH
  4.Fortnow, L., Santhanam, R.: Infeasibility of instance compression and succinct PCPs for NP. J. Comput. Syst. Sci. 77(1), 91–106 (2011)MathSciNet CrossRef MATH
  5.Bodlaender, H., Downey, R., Fellows, M., Hermelin, D.: On problems without polynomial kernels. J. Comput. Syst. Sci. 75(8), 423–434 (2009)MathSciNet CrossRef MATH
  6.Harnik, D., Naor, M.: On the compressibility of NP instances and cryptographic applications. SIAM J. Comput. 39(5), 1667–1713 (2010)MathSciNet CrossRef MATH
  7.Buhrman, H., Hitchcock, J.: NP-hard sets are exponentially dense unless coNP is contained in NP/poly. In: 23rd Annual IEEE Conference on Computational Complexity, CCC 2008, pp. 1–7. IEEE, New York, June 2008
  8.Drucker, A.: New limits to classical and quantum instance compression. SIAM J. Comput. 44(5), 1443–1479 (2015)MathSciNet CrossRef MATH
  9.Post, E.: Recursively enumerable sets of positive integers and their decision problems. Bullet. Am. Math. Soc. 50(5), 284–316 (1944)MathSciNet CrossRef MATH
  10.Soare, R.: Recursively Enumerable Sets and Degrees. Springer, Berlin (1987)CrossRef MATH
  11.Cook, S.: The complexity of theorem-proving procedures. In: Proceedings of the 3rd ACM Symposium on the Theory of Computing, pp. 151–158. ACM, New York (1971)
  12.Karp, R.: Reducibility among combinatorial problems. In: Miller, R., Thatcher, J. (eds.) Complexity of Computer Computations. The IBM Research Symposia Series, pp. 85–103. Springer, New York (1972). doi:10.​1007/​978-1-4684-2001-2_​9 CrossRef
  13.Ladner, R.: On the structure of polynomial time reducibility. J. ACM 22, 155–171 (1975)MathSciNet CrossRef MATH
  14.Fortnow, L., Santhanam, R.: Robust Simulations and Significant Separations, pp. 569–580. Springer, Heidelberg (2011)MATH
  15.Fortnow, L., Santhanam, R.: New non-uniform lower bounds for uniform classes. In: Raz, R. (ed.) 31st Conference on Computational Complexity (CCC 2016). Leibniz International Proceedings in Informatics (LIPIcs), vol. 50, pp. 19:1–19:14. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany (2016)
  
• 作者单位：Lance Fortnow (19)
  
  19. Georgia Institute of Technology, Atlanta, USA
  
• 丛书名：Computability and Complexity
• ISBN：978-3-319-50062-1
• 卷排序：10010

文摘

Rod Downey and I have had a fruitful relationship though direct and indirect collaboration. I explore two research directions, the limitations of distillation and instance compression, and whether or not we can create NP-incomplete problems without punching holes in NP-complete problems.