Mathematical Logic Seminar

Why is solving the P vs NP problem so damn hard?

Sala 6.2.33, Ciências ULisboa (com transmissão via Zoom)

Por Bruno Loff (Universidade do Porto).

I will give a board-and-chalk-and-informal-talk presentation about the difficulty of proving lower-bounds in computational complexity. 

The P vs NP problem is one of the most famous unsolved problems in mathematics. One may phrase the P vs NP question in various equivalent ways. One way, which is not completely equivalent, but almost, is the following ("P/poly vs NP problem"). Does there exist a small Boolean circuit which solves the CLIQUE problem? I.e., does there exist a poly(N)-size Boolean circuit which, when given as input the NxN adjacency matrix of an undirected graph, decides whether the graph has a clique of size N/2?

Complexity theorists, me included, believe that the answer is no. We believe that there exists a super-polynomial "lower-bound" on the complexity of CLIQUE. Many people have tried proving such a lower-bound, and so far all have failed. But why? Why is the problem so difficult?

In the late 1980s, Alexander Razborov proved that there exist no poly(N)-size "monotone" circuits for solving CLIQUE. Namely, if we forbid the Boolean circuit from doing negations, so they can only do ORs and ANDs, then polysize circuits cannot solve the CLIQUE problem. He (and many others) then tried to prove the same result for ordinary circuits (with negation gates). And he failed (and they all failed, too). But along the way he (and many others) proved many different lower-bounds. Lower-bounds for simpler kinds of circuits (e.g. constant-depth), lower-bounds for communication protocols (a different but related computational model), and lower-bounds for other models. Razborov proved these lower-bounds, and he also thought long and hard about why lower-bounds against Boolean circuits were so difficult to prove.

In 1994, Razborov and Stephen Rudich presented their paper, "natural proofs", which had a very reasonable explanation for why circuit lower-bounds were difficult to prove. They showed, remarkably, that every single lower-bound proof that was known at the time had a certain "logical structure" (or could be made to have such a structure by small changes to the argument). This logical structure made the proof very simple and natural, and they called proofs with such a structure "natural proofs". Then they showed that super-polynomial lower-bounds on CLIQUE cannot be shown using natural proofs, unless certain cryptographic primitives, such as factoring, are unsecure. This is a kind of informal independence result. (Based on the natural proofs result, Razborov also later proved formal independence results, showing that P vs NP is independent of certain weak systems of arithmetic, but I do now know the details of those.)

In one fell swoop, Razborov and Rudich ruled out every single lower-bound technique known at the time, saying: these techniques are not enough to solve the P vs NP problem (unless cryptography is insecure). To a very large extent this barrier still applies today, as almost all the lower-bound proofs that we know are natural proofs, i.e., they have the very same logical structure as the proofs known since the 1980s.

In this seminar, I will explain what is a "natural proof", and why it is reasonable to expect that no natural proof can solve the P vs NP problem. Only a few words will be said about some of my research and how it connects to this topic.


Zoom | Meeting ID: 837 8989 1971

16h00
CMAFcIO - Centro de Matemática, Aplicações Fundamentais e Investigação Operacional

Uma atividade coordenada por Vítor Lapa Fernandes (aluno de CIÊNCIAS), promotor do projeto vencedor do concurso de bolsas para jovens artistas, ativistas e criadores desenvolvido pelo Festival Política e pelo Instituto Português do Desporto e Juventude.

Projeto de Tese (Doutoramento em Biodiversidade, Genética e Evolução), por Fátima Inácio.

Seminário do Centro de Física Teórica e Computacional, por Pablo Sartori (Instituto Gulbenkian de Ciência, Oeiras, Portugal).

Banner do Dia de Ciências 2025_v2

A 29 de abril assinalamos o 114.º aniversário de CIÊNCIAS.

Junte-se a nós no Grande Auditório de CIÊNCIAS para uma tarde de celebração que reúne toda a comunidade da Faculdade.

Seminário de Lógica Matemática, por Charles Morgan (UFBA).

Pavilhão de Portugal

Na ocasião, será ainda inaugurada a exposição “Meu matalote e amigo Luís de Camões” que explora a figura do poeta através de um diálogo entre arte, literatura e património histórico. A cerimónia contará ainda com uma programação paralela que será divulgada em detalhe oportunamente.

Pormenor de pintura representativa da cidade de Aden

O curso, com Jorge Flores (CIUHCT), oferece uma visão da história da Ásia a partir de cidades portuárias cruciais nas relações com o Ocidente.

O Tec Labs lançou a marca MindTec com o objetivo de promover um processo participativo de rebranding interno, assente na escuta ativa da sua comunidade. Esta sessão marca o arranque oficial do projeto e será um momento-chave para apresentar os seus objetivos, envolver a comunidade e começar a recolher perceções, expectativas e desafios relacionados com a comunicação no ecossistema.

Fotografia de fábrica a emitir poluição para a atmosfera

The course aims at enabling the participants to use different methods to measure the impacts of pollutants on ecosystems.

Logótipo C-Academy

O curso oferece uma base sólida sobre os fundamentos e práticas essenciais para proteger sistemas e dados num mundo cada vez mais digital - candidaturas até 13 de abril.

Curso destinado a todos que necessitem de realizar análise de dados com recurso ao R.

Seminário do Centro de Física Teórica e Computacional, por Fábio Chalub (NOVA Math, Universidade NOVA de Lisboa, Portugal).

Banner Dia Aberto de CIÊNCIAS 2025.

Bem-vindos a Ciências ULisboa!

Um concurso de programação dirigido aos alunos do ensino secundário (11.º e 12.º anos), que visa promover a prática e o gosto pela programação.

Fotografia de Chapim-azul

The goal of this course is to provide the participants with the most recent and practical knowledge on the use of Functional Diversity.

O encontro tem como objetivo divulgar e promover os resultados da investigação produzidos nos dois pólos do Centro de Química Estrutural (CIÊNCIAS e IST), estimulando a criatividade, o trabalho interdisciplinar e o espírito científico.

Mão a segurar em globo de vidro

Curso acreditado pelo CCPFC para efeitos de progressão na carreira dos professores na dimensão cientifico-pedagógica dos grupos 230, 420, 510, 520 e 560, com candidaturas até 30 de abril.

Título/data/local do evento, logótipos das entidades organizadoras e fotografia de peixe

The event aims to facilitate the exchange of information and knowledge among professionals to advance the understanding, collaboration and capabilities of aquaculture to respond to the impact of climate change in a rapidly changing global environment.

Uma oportunidade única para interagir com a comunidade global de computação científica, com inscrições (preço reduzido) até 02 de maio.

Logótipo Moodle

Ação de formação para docentes e investigadores de CIÊNCIAS.

Título/data/local do evento e iconografia representativa de energias renováveis

Inscrições até 16 de maio! Junta-te a esta revolução energética e faz a diferença!

Químico a escrever fórmulas num quadro

Curso acreditado para efeitos de progressão na carreira dos professores do Ensino Básico e Secundário do Grupo 510 (CCPFC/ACC-118288/22), com candidaturas até 18 de maio.

Curso destinado a estudantes de Mestrado e de Doutoramento, bem como a profissionais que desenvolvam investigação científica na área da saúde.

Título/data/local do evento e fotografia do mar

Quais são os conceitos-chave para enfrentar os atuais desafios marinhos e costeiros? 

Representação de programação R

This course aims at providing students with basic knowledge of R programming, allowing them to manipulate and visualize data with R.

Páginas