Ranks of gauge groups and an NP-complete problem on the Landscape

Name: Work Video:
Duration: 3 min 30 s
Description: We prove that the problem of determination of factor gauge groups given the rank of the gauge group at any given vacuum in the Landscape is in the computational complexity class NPC. This extends a result of Denef and Douglas on the computational complexity of determination of the value of the cosmological constant in the Landscape.
Abhijnan Rej
{'id': 'https://openalex.org/W4299494376', 'doi': 'https://doi.org/10.48550/arxiv.1212.3912', 'title': 'Ranks of gauge groups and an NP-complete problem on the Landscape', 'display_name': 'Ranks of gauge groups and an NP-complete problem on the Landscape', 'publication_year': 2012, 'publication_date': '2012-01-01', 'ids': {'openalex': 'https://openalex.org/W4299494376', 'doi': 'https://doi.org/10.48550/arxiv.1212.3912'}, 'language': 'en', 'primary_location': {'is_oa': True, 'landing_page_url': 'https://arxiv.org/abs/1212.3912', 'pdf_url': None, 'source': {'id': 'https://openalex.org/S4306400194', 'display_name': 'arXiv (Cornell University)', 'issn_l': None, 'issn': None, 'is_oa': True, 'is_in_doaj': False, 'is_core': False, 'host_organization': 'https://openalex.org/I205783295', 'host_organization_name': 'Cornell University', 'host_organization_lineage': ['https://openalex.org/I205783295'], 'host_organization_lineage_names': ['Cornell University'], 'type': 'repository'}, 'license': 'other-oa', 'license_id': 'https://openalex.org/licenses/other-oa', 'version': 'submittedVersion', 'is_accepted': False, 'is_published': False}, 'type': 'preprint', 'type_crossref': 'posted-content', 'indexed_in': ['arxiv', 'datacite'], 'open_access': {'is_oa': True, 'oa_status': 'green', 'oa_url': 'https://arxiv.org/abs/1212.3912', 'any_repository_has_fulltext': True}, 'authorships': [{'author_position': 'first', 'author': {'id': 'https://openalex.org/A5022504333', 'display_name': 'Abhijnan Rej', 'orcid': None}, 'institutions': [], 'countries': [], 'is_corresponding': True, 'raw_author_name': 'Rej, Abhijnan', 'raw_affiliation_strings': [], 'affiliations': []}], 'institution_assertions': [], 'countries_distinct_count': 0, 'institutions_distinct_count': 0, 'corresponding_author_ids': ['https://openalex.org/A5022504333'], 'corresponding_institution_ids': [], 'apc_list': None, 'apc_paid': None, 'fwci': None, 'has_fulltext': False, 'cited_by_count': 0, 'citation_normalized_percentile': {'value': 0.0, 'is_in_top_1_percent': False, 'is_in_top_10_percent': False}, 'cited_by_percentile_year': {'min': 0, 'max': 64}, 'biblio': {'volume': None, 'issue': None, 'first_page': None, 'last_page': None}, 'is_retracted': False, 'is_paratext': False, 'primary_topic': {'id': 'https://openalex.org/T10025', 'display_name': 'Black Holes and Theoretical Physics', 'score': 0.9799, 'subfield': {'id': 'https://openalex.org/subfields/3106', 'display_name': 'Nuclear and High Energy Physics'}, 'field': {'id': 'https://openalex.org/fields/31', 'display_name': 'Physics and Astronomy'}, 'domain': {'id': 'https://openalex.org/domains/3', 'display_name': 'Physical Sciences'}}, 'topics': [{'id': 'https://openalex.org/T10025', 'display_name': 'Black Holes and Theoretical Physics', 'score': 0.9799, 'subfield': {'id': 'https://openalex.org/subfields/3106', 'display_name': 'Nuclear and High Energy Physics'}, 'field': {'id': 'https://openalex.org/fields/31', 'display_name': 'Physics and Astronomy'}, 'domain': {'id': 'https://openalex.org/domains/3', 'display_name': 'Physical Sciences'}}, {'id': 'https://openalex.org/T11415', 'display_name': 'Noncommutative and Quantum Gravity Theories', 'score': 0.977, 'subfield': {'id': 'https://openalex.org/subfields/3109', 'display_name': 'Statistical and Nonlinear Physics'}, 'field': {'id': 'https://openalex.org/fields/31', 'display_name': 'Physics and Astronomy'}, 'domain': {'id': 'https://openalex.org/domains/3', 'display_name': 'Physical Sciences'}}, {'id': 'https://openalex.org/T13234', 'display_name': 'advanced mathematical theories', 'score': 0.9705, 'subfield': {'id': 'https://openalex.org/subfields/2610', 'display_name': 'Mathematical Physics'}, 'field': {'id': 'https://openalex.org/fields/26', 'display_name': 'Mathematics'}, 'domain': {'id': 'https://openalex.org/domains/3', 'display_name': 'Physical Sciences'}}], 'keywords': [{'id': 'https://openalex.org/keywords/rank', 'display_name': 'Rank (graph theory)', 'score': 0.70244235}, {'id': 'https://openalex.org/keywords/gauge-group', 'display_name': 'Gauge group', 'score': 0.6162944}, {'id': 'https://openalex.org/keywords/constant', 'display_name': 'Constant (computer programming)', 'score': 0.5713586}, {'id': 'https://openalex.org/keywords/value', 'display_name': 'Value (mathematics)', 'score': 0.5247728}], 'concepts': [{'id': 'https://openalex.org/C40976572', 'wikidata': 'https://www.wikidata.org/wiki/Q2330873', 'display_name': 'Gauge (firearms)', 'level': 2, 'score': 0.749568}, {'id': 'https://openalex.org/C164226766', 'wikidata': 'https://www.wikidata.org/wiki/Q7293202', 'display_name': 'Rank (graph theory)', 'level': 2, 'score': 0.70244235}, {'id': 'https://openalex.org/C2779430453', 'wikidata': 'https://www.wikidata.org/wiki/Q15260871', 'display_name': 'Gauge group', 'level': 3, 'score': 0.6162944}, {'id': 'https://openalex.org/C2777027219', 'wikidata': 'https://www.wikidata.org/wiki/Q1284190', 'display_name': 'Constant (computer programming)', 'level': 2, 'score': 0.5713586}, {'id': 'https://openalex.org/C2777212361', 'wikidata': 'https://www.wikidata.org/wiki/Q5127848', 'display_name': 'Class (philosophy)', 'level': 2, 'score': 0.53115404}, {'id': 'https://openalex.org/C2776291640', 'wikidata': 'https://www.wikidata.org/wiki/Q2912517', 'display_name': 'Value (mathematics)', 'level': 2, 'score': 0.5247728}, {'id': 'https://openalex.org/C33923547', 'wikidata': 'https://www.wikidata.org/wiki/Q395', 'display_name': 'Mathematics', 'level': 0, 'score': 0.47251707}, {'id': 'https://openalex.org/C2781311116', 'wikidata': 'https://www.wikidata.org/wiki/Q83306', 'display_name': 'Group (periodic table)', 'level': 2, 'score': 0.4260331}, {'id': 'https://openalex.org/C179799912', 'wikidata': 'https://www.wikidata.org/wiki/Q205084', 'display_name': 'Computational complexity theory', 'level': 2, 'score': 0.4242403}, {'id': 'https://openalex.org/C181830111', 'wikidata': 'https://www.wikidata.org/wiki/Q214850', 'display_name': 'Gauge theory', 'level': 2, 'score': 0.39562595}, {'id': 'https://openalex.org/C33332235', 'wikidata': 'https://www.wikidata.org/wiki/Q18362', 'display_name': 'Theoretical physics', 'level': 1, 'score': 0.3792706}, {'id': 'https://openalex.org/C121332964', 'wikidata': 'https://www.wikidata.org/wiki/Q413', 'display_name': 'Physics', 'level': 0, 'score': 0.36738044}, {'id': 'https://openalex.org/C202444582', 'wikidata': 'https://www.wikidata.org/wiki/Q837863', 'display_name': 'Pure mathematics', 'level': 1, 'score': 0.3207779}, {'id': 'https://openalex.org/C114614502', 'wikidata': 'https://www.wikidata.org/wiki/Q76592', 'display_name': 'Combinatorics', 'level': 1, 'score': 0.30579388}, {'id': 'https://openalex.org/C41008148', 'wikidata': 'https://www.wikidata.org/wiki/Q21198', 'display_name': 'Computer science', 'level': 0, 'score': 0.24905783}, {'id': 'https://openalex.org/C11413529', 'wikidata': 'https://www.wikidata.org/wiki/Q8366', 'display_name': 'Algorithm', 'level': 1, 'score': 0.20008916}, {'id': 'https://openalex.org/C37914503', 'wikidata': 'https://www.wikidata.org/wiki/Q156495', 'display_name': 'Mathematical physics', 'level': 1, 'score': 0.16515306}, {'id': 'https://openalex.org/C62520636', 'wikidata': 'https://www.wikidata.org/wiki/Q944', 'display_name': 'Quantum mechanics', 'level': 1, 'score': 0.1618295}, {'id': 'https://openalex.org/C205649164', 'wikidata': 'https://www.wikidata.org/wiki/Q1071', 'display_name': 'Geography', 'level': 0, 'score': 0.15122956}, {'id': 'https://openalex.org/C105795698', 'wikidata': 'https://www.wikidata.org/wiki/Q12483', 'display_name': 'Statistics', 'level': 1, 'score': 0.11626485}, {'id': 'https://openalex.org/C154945302', 'wikidata': 'https://www.wikidata.org/wiki/Q11660', 'display_name': 'Artificial intelligence', 'level': 1, 'score': 0.10764739}, {'id': 'https://openalex.org/C166957645', 'wikidata': 'https://www.wikidata.org/wiki/Q23498', 'display_name': 'Archaeology', 'level': 1, 'score': 0.0}, {'id': 'https://openalex.org/C199360897', 'wikidata': 'https://www.wikidata.org/wiki/Q9143', 'display_name': 'Programming language', 'level': 1, 'score': 0.0}], 'mesh': [], 'locations_count': 3, 'locations': [{'is_oa': True, 'landing_page_url': 'https://arxiv.org/abs/1212.3912', 'pdf_url': None, 'source': {'id': 'https://openalex.org/S4306400194', 'display_name': 'arXiv (Cornell University)', 'issn_l': None, 'issn': None, 'is_oa': True, 'is_in_doaj': False, 'is_core': False, 'host_organization': 'https://openalex.org/I205783295', 'host_organization_name': 'Cornell University', 'host_organization_lineage': ['https://openalex.org/I205783295'], 'host_organization_lineage_names': ['Cornell University'], 'type': 'repository'}, 'license': 'other-oa', 'license_id': 'https://openalex.org/licenses/other-oa', 'version': 'submittedVersion', 'is_accepted': False, 'is_published': False}, {'is_oa': True, 'landing_page_url': 'http://arxiv.org/abs/1212.3912', 'pdf_url': 'http://arxiv.org/pdf/1212.3912', 'source': {'id': 'https://openalex.org/S4306400194', 'display_name': 'arXiv (Cornell University)', 'issn_l': None, 'issn': None, 'is_oa': True, 'is_in_doaj': False, 'is_core': False, 'host_organization': 'https://openalex.org/I205783295', 'host_organization_name': 'Cornell University', 'host_organization_lineage': ['https://openalex.org/I205783295'], 'host_organization_lineage_names': ['Cornell University'], 'type': 'repository'}, 'license': None, 'license_id': None, 'version': 'submittedVersion', 'is_accepted': False, 'is_published': False}, {'is_oa': False, 'landing_page_url': 'https://api.datacite.org/dois/10.48550/arxiv.1212.3912', 'pdf_url': None, 'source': {'id': 'https://openalex.org/S4393179698', 'display_name': 'DataCite API', 'issn_l': None, 'issn': None, 'is_oa': True, 'is_in_doaj': False, 'is_core': False, 'host_organization': 'https://openalex.org/I4210145204', 'host_organization_name': 'DataCite', 'host_organization_lineage': ['https://openalex.org/I4210145204'], 'host_organization_lineage_names': ['DataCite'], 'type': 'metadata'}, 'license': None, 'license_id': None, 'version': None}], 'best_oa_location': {'is_oa': True, 'landing_page_url': 'https://arxiv.org/abs/1212.3912', 'pdf_url': None, 'source': {'id': 'https://openalex.org/S4306400194', 'display_name': 'arXiv (Cornell University)', 'issn_l': None, 'issn': None, 'is_oa': True, 'is_in_doaj': False, 'is_core': False, 'host_organization': 'https://openalex.org/I205783295', 'host_organization_name': 'Cornell University', 'host_organization_lineage': ['https://openalex.org/I205783295'], 'host_organization_lineage_names': ['Cornell University'], 'type': 'repository'}, 'license': 'other-oa', 'license_id': 'https://openalex.org/licenses/other-oa', 'version': 'submittedVersion', 'is_accepted': False, 'is_published': False}, 'sustainable_development_goals': [], 'grants': [], 'datasets': [], 'versions': [], 'referenced_works_count': 0, 'referenced_works': [], 'related_works': ['https://openalex.org/W4299494376', 'https://openalex.org/W3101326078', 'https://openalex.org/W3082972421', 'https://openalex.org/W2963184967', 'https://openalex.org/W2606876831', 'https://openalex.org/W2402996660', 'https://openalex.org/W2187972090', 'https://openalex.org/W2033565855', 'https://openalex.org/W2024271032', 'https://openalex.org/W1975115845'], 'abstract_inverted_index': {'We': [0], 'prove': [1], 'that': [2], 'the': [3, 12, 15, 23, 27, 41, 47, 50, 54], 'problem': [4], 'of': [5, 7, 14, 36, 44, 46, 49], 'determination': [6, 45], 'factor': [8], 'gauge': [9, 16], 'groups': [10], 'given': [11, 20], 'rank': [13], 'group': [17], 'at': [18], 'any': [19], 'vacuum': [21], 'in': [22, 26, 53], 'Landscape': [24], 'is': [25], 'computational': [28, 42], 'complexity': [29, 43], 'class': [30], 'NPC.': [31], 'This': [32], 'extends': [33], 'a': [34], 'result': [35], 'Denef': [37], 'and': [38], 'Douglas': [39], 'on': [40], 'value': [48], 'cosmological': [51], 'constant': [52], 'Landscape.': [55]}, 'cited_by_api_url': 'https://api.openalex.org/works?filter=cites:W4299494376', 'counts_by_year': [], 'updated_date': '2024-12-07T05:11:42.911120', 'created_date': '2022-10-02'}
Publication Information

Basic Information

Access and Citation

AI Researcher Chatbot

Primary Location

Authors

Topics

Keywords

Related Works
