Some consequences of our failure to prove non-linear lower bounds on explicit functions

Name: Some consequences of our failure to prove non-linear lower bounds on explicit functions
Creator: Richard J. Lipton
Keywords: 0102 computer and information sciences, 01 natural sciences

Richard J. Lipton

Found an issue? Give us feedback

https://doi.org/10.1...arrow_drop_down

https://doi.org/10.1109/sct.19...

Article . 2002 . Peer-reviewed

Data sources: Crossref

DBLP

Conference object

Data sources: DBLP

https://dx.doi.org/10.1109/sct...

Article

Data sources: Microsoft Academic Graph

Some consequences of our failure to prove non-linear lower bounds on explicit functions

descriptionPublicationkeyboard_double_arrow_right Article , Conference object 17 Dec 2002Publisher:IEEE Comput. Soc. PressJournal:Proceedings of IEEE 9th Annual Conference on Structure in Complexity Theory

Authors: Richard J. Lipton;

doi: 10.1109/sct.1994.315815

Some consequences of our failure to prove non-linear lower bounds on explicit functions

- Summary
- Related research
  (2)
- Metrics

Abstract

Investigates the consequences of assuming that no explicit function has non-polynomial size Boolean circuit complexity. There are many consequences of this assumption. For example, it immediately proves that P does not equal NP. It also has ramifications for the length of certain interactive proofs. >

Related Organizations

College of New Jersey
United States

2 Research products, page 1 of 1

Generic hardness of the Boolean satisfiability problem
2017IsAmongTopNSimilarDocuments
ON GENERIC NP-COMPLETENESS OF THE BOOLEAN SATISFIABILITY PROBLEM
2017IsAmongTopNSimilarDocuments

Impact byBIP!

	selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	3
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Average
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Average
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Average