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
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.

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.

Logótipo MindTec

5 de maio - lançamento do projeto de rebranding interno que pretende repensar e redesenhar, em conjunto com a nossa comunidade académica, a identidade do Tec Labs.

Performance teatral

A apresentação pública do FATAL - Festival Anual de Teatro Académico de Lisboa contará com uma homenagem a Rogério de Carvalho, figura marcante do Teatro português, sendo igualmente apresentada a programação do festival.

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

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

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.

Banner do Dia Aberto 2025 - Trilho dos Caloiros

Bem-vindos a Ciências ULisboa!

Vista a partir de cima de pessoas a trabalharem sobre uma mesa de madeira

CIÊNCIAS desenvolve um conjunto de atividades de apoio aos Doutorandos, periodicamente enquadradas no âmbito do PhD Support Programme.

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.

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.

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.

The conference focuses on "Algebra and its role in Computer Science", with special emphasis on the areas of study related to the work of M. V. Volkov, such as semigroups and automata.

Logótipo do Verão na ULisboa, sobre um fundo azul

Candidaturas a partir de 07 de abril!

Representação de programação R

This course aims at providing students with statistical knowledge and tools to manipulate, analyse and visualise biological data with R. Introduction to modeling, simulations and Bayesian statistics.

Computability in Europe (CiE) is an interdisciplinary series of international conferences organised by the Association Computability in Europe (ACiE).

Páginas