Improving exhaustive search implies superpolynomial lower bounds

Name: Work Video:
Duration: 3 min 30 s
Description: The P vs NP problem arose from the question of whether exhaustive search is necessary for problems with short verifiable solutions. We still do not know if even a slight algorithmic improvement over exhaustive search is universally possible for all NP problems, and to date no major consequences have been derived from the assumption that an improvement exists.
Ryan Williams
{'id': 'https://openalex.org/W2007121506', 'doi': 'https://doi.org/10.1145/1806689.1806723', 'title': 'Improving exhaustive search implies superpolynomial lower bounds', 'display_name': 'Improving exhaustive search implies superpolynomial lower bounds', 'publication_year': 2010, 'publication_date': '2010-06-05', 'ids': {'openalex': 'https://openalex.org/W2007121506', 'doi': 'https://doi.org/10.1145/1806689.1806723', 'mag': '2007121506'}, 'language': 'en', 'primary_location': {'is_oa': False, 'landing_page_url': 'https://doi.org/10.1145/1806689.1806723', 'pdf_url': None, 'source': None, 'license': None, 'license_id': None, 'version': None, 'is_accepted': False, 'is_published': False}, 'type': 'article', 'type_crossref': 'proceedings-article', 'indexed_in': ['crossref'], 'open_access': {'is_oa': False, 'oa_status': 'closed', 'oa_url': None, 'any_repository_has_fulltext': False}, 'authorships': [{'author_position': 'first', 'author': {'id': 'https://openalex.org/A5063871533', 'display_name': 'Ryan Williams', 'orcid': 'https://orcid.org/0000-0003-2326-2233'}, 'institutions': [{'id': 'https://openalex.org/I4210085935', 'display_name': 'IBM Research - Almaden', 'ror': 'https://ror.org/005w8dd04', 'country_code': 'US', 'type': 'facility', 'lineage': ['https://openalex.org/I1341412227', 'https://openalex.org/I4210085935', 'https://openalex.org/I4210114115']}], 'countries': ['US'], 'is_corresponding': True, 'raw_author_name': 'Ryan Williams', 'raw_affiliation_strings': ['IBM Almaden Research Center, San Jose, CA, USA'], 'affiliations': [{'raw_affiliation_string': 'IBM Almaden Research Center, San Jose, CA, USA', 'institution_ids': ['https://openalex.org/I4210085935']}]}], 'institution_assertions': [], 'countries_distinct_count': 1, 'institutions_distinct_count': 1, 'corresponding_author_ids': ['https://openalex.org/A5063871533'], 'corresponding_institution_ids': ['https://openalex.org/I4210085935'], 'apc_list': None, 'apc_paid': None, 'fwci': 14.959, 'has_fulltext': True, 'fulltext_origin': 'ngrams', 'cited_by_count': 77, 'citation_normalized_percentile': {'value': 0.985932, 'is_in_top_1_percent': False, 'is_in_top_10_percent': True}, 'cited_by_percentile_year': {'min': 96, 'max': 97}, 'biblio': {'volume': None, 'issue': None, 'first_page': '231', 'last_page': '240'}, 'is_retracted': False, 'is_paratext': False, 'primary_topic': {'id': 'https://openalex.org/T10720', 'display_name': 'Complexity and Algorithms in Graphs', 'score': 0.9998, 'subfield': {'id': 'https://openalex.org/subfields/1703', 'display_name': 'Computational Theory and Mathematics'}, 'field': {'id': 'https://openalex.org/fields/17', 'display_name': 'Computer Science'}, 'domain': {'id': 'https://openalex.org/domains/3', 'display_name': 'Physical Sciences'}}, 'topics': [{'id': 'https://openalex.org/T10720', 'display_name': 'Complexity and Algorithms in Graphs', 'score': 0.9998, 'subfield': {'id': 'https://openalex.org/subfields/1703', 'display_name': 'Computational Theory and Mathematics'}, 'field': {'id': 'https://openalex.org/fields/17', 'display_name': 'Computer Science'}, 'domain': {'id': 'https://openalex.org/domains/3', 'display_name': 'Physical Sciences'}}, {'id': 'https://openalex.org/T12288', 'display_name': 'Optimization and Search Problems', 'score': 0.9992, 'subfield': {'id': 'https://openalex.org/subfields/1705', 'display_name': 'Computer Networks and Communications'}, 'field': {'id': 'https://openalex.org/fields/17', 'display_name': 'Computer Science'}, 'domain': {'id': 'https://openalex.org/domains/3', 'display_name': 'Physical Sciences'}}, {'id': 'https://openalex.org/T10374', 'display_name': 'Advanced Graph Theory Research', 'score': 0.9989, 'subfield': {'id': 'https://openalex.org/subfields/1703', 'display_name': 'Computational Theory and Mathematics'}, 'field': {'id': 'https://openalex.org/fields/17', 'display_name': 'Computer Science'}, 'domain': {'id': 'https://openalex.org/domains/3', 'display_name': 'Physical Sciences'}}], 'keywords': [], 'concepts': [{'id': 'https://openalex.org/C85847156', 'wikidata': 'https://www.wikidata.org/wiki/Q59015987', 'display_name': 'Verifiable secret sharing', 'level': 3, 'score': 0.8070636}, {'id': 'https://openalex.org/C41008148', 'wikidata': 'https://www.wikidata.org/wiki/Q21198', 'display_name': 'Computer science', 'level': 0, 'score': 0.49682382}, {'id': 'https://openalex.org/C33923547', 'wikidata': 'https://www.wikidata.org/wiki/Q395', 'display_name': 'Mathematics', 'level': 0, 'score': 0.44601348}, {'id': 'https://openalex.org/C80444323', 'wikidata': 'https://www.wikidata.org/wiki/Q2878974', 'display_name': 'Theoretical computer science', 'level': 1, 'score': 0.35102773}, {'id': 'https://openalex.org/C11413529', 'wikidata': 'https://www.wikidata.org/wiki/Q8366', 'display_name': 'Algorithm', 'level': 1, 'score': 0.32640415}, {'id': 'https://openalex.org/C177264268', 'wikidata': 'https://www.wikidata.org/wiki/Q1514741', 'display_name': 'Set (abstract data type)', 'level': 2, 'score': 0.07192248}, {'id': 'https://openalex.org/C199360897', 'wikidata': 'https://www.wikidata.org/wiki/Q9143', 'display_name': 'Programming language', 'level': 1, 'score': 0.0}], 'mesh': [], 'locations_count': 1, 'locations': [{'is_oa': False, 'landing_page_url': 'https://doi.org/10.1145/1806689.1806723', 'pdf_url': None, 'source': None, 'license': None, 'license_id': None, 'version': None, 'is_accepted': False, 'is_published': False}], 'best_oa_location': None, 'sustainable_development_goals': [], 'grants': [], 'datasets': [], 'versions': [], 'referenced_works_count': 64, 'referenced_works': ['https://openalex.org/W107779203', 'https://openalex.org/W1515598460', 'https://openalex.org/W1527197079', 'https://openalex.org/W1542263829', 'https://openalex.org/W1570425181', 'https://openalex.org/W1576180980', 'https://openalex.org/W1584670745', 'https://openalex.org/W159299097', 'https://openalex.org/W1748501741', 'https://openalex.org/W1966819396', 'https://openalex.org/W1970089350', 'https://openalex.org/W1971724037', 'https://openalex.org/W1973852671', 'https://openalex.org/W1985572324', 'https://openalex.org/W1994584977', 'https://openalex.org/W1995725694', 'https://openalex.org/W1996834809', 'https://openalex.org/W1999061527', 'https://openalex.org/W2002992445', 'https://openalex.org/W2005223599', 'https://openalex.org/W2006337932', 'https://openalex.org/W2006558104', 'https://openalex.org/W2009147258', 'https://openalex.org/W2012948111', 'https://openalex.org/W2018964411', 'https://openalex.org/W2026036943', 'https://openalex.org/W2027999353', 'https://openalex.org/W2039529128', 'https://openalex.org/W2040654780', 'https://openalex.org/W2045334235', 'https://openalex.org/W2045519569', 'https://openalex.org/W2045717693', 'https://openalex.org/W2047749000', 'https://openalex.org/W2075449032', 'https://openalex.org/W2079357831', 'https://openalex.org/W2083237534', 'https://openalex.org/W2083747727', 'https://openalex.org/W2095318887', 'https://openalex.org/W2114870555', 'https://openalex.org/W2130190334', 'https://openalex.org/W2133527541', 'https://openalex.org/W2137407595', 'https://openalex.org/W2140270919', 'https://openalex.org/W2140797111', 'https://openalex.org/W2144345645', 'https://openalex.org/W21453999', 'https://openalex.org/W2150123893', 'https://openalex.org/W2158747250', 'https://openalex.org/W2159892713', 'https://openalex.org/W2164606052', 'https://openalex.org/W2179532697', 'https://openalex.org/W2242954222', 'https://openalex.org/W2296506534', 'https://openalex.org/W2395895426', 'https://openalex.org/W2612879297', 'https://openalex.org/W2913688336', 'https://openalex.org/W2998808137', 'https://openalex.org/W36639738', 'https://openalex.org/W37923608', 'https://openalex.org/W4206807714', 'https://openalex.org/W4213071546', 'https://openalex.org/W4256418102', 'https://openalex.org/W4285719527', 'https://openalex.org/W586528178'], 'related_works': ['https://openalex.org/W2748952813', 'https://openalex.org/W2377292126', 'https://openalex.org/W2365629437', 'https://openalex.org/W2355730523', 'https://openalex.org/W2350372928', 'https://openalex.org/W2348330439', 'https://openalex.org/W2072918937', 'https://openalex.org/W2023935927', 'https://openalex.org/W181049489', 'https://openalex.org/W152021879'], 'abstract_inverted_index': {'The': [0], 'P': [1], 'vs': [2], 'NP': [3, 40], 'problem': [4], 'arose': [5], 'from': [6, 51], 'the': [7, 52], 'question': [8], 'of': [9], 'whether': [10], 'exhaustive': [11, 33], 'search': [12, 34], 'is': [13, 35], 'necessary': [14], 'for': [15, 38], 'problems': [16], 'with': [17], 'short': [18], 'verifiable': [19], 'solutions.': [20], 'We': [21], 'still': [22], 'do': [23], 'not': [24], 'know': [25], 'if': [26], 'even': [27], 'a': [28], 'slight': [29], 'algorithmic': [30], 'improvement': [31, 56], 'over': [32], 'universally': [36], 'possible': [37], 'all': [39], 'problems,': [41], 'and': [42], 'to': [43], 'date': [44], 'no': [45], 'major': [46], 'consequences': [47], 'have': [48], 'been': [49], 'derived': [50], 'assumption': [53], 'that': [54], 'an': [55], 'exists.': [57]}, 'cited_by_api_url': 'https://api.openalex.org/works?filter=cites:W2007121506', 'counts_by_year': [{'year': 2023, 'cited_by_count': 1}, {'year': 2022, 'cited_by_count': 1}, {'year': 2021, 'cited_by_count': 4}, {'year': 2020, 'cited_by_count': 1}, {'year': 2019, 'cited_by_count': 2}, {'year': 2018, 'cited_by_count': 2}, {'year': 2017, 'cited_by_count': 1}, {'year': 2016, 'cited_by_count': 2}, {'year': 2015, 'cited_by_count': 7}, {'year': 2014, 'cited_by_count': 7}, {'year': 2013, 'cited_by_count': 14}, {'year': 2012, 'cited_by_count': 13}], 'updated_date': '2024-12-23T06:46:54.956458', 'created_date': '2016-06-24'}
Publication Information

Basic Information

Access and Citation

AI Researcher Chatbot

Primary Location

Authors

Topics

Keywords

Related Works
