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
Título "Bolsas de Doutoramento Unite! ULisboa", logótipos das entidades promotoras e fotografia de jovem investigadora a utilizar um laptop na esplanada de um café

O 3.º concurso decorre de 29 de março a 30 de abril.

A atividade consiste numa caminhada pelo Lousal, passando por vários pontos importantes da história da Mina do Lousal.

BioISI Research Seminar, por Duarte Figueiredo (Max Planck Institute of Molecular Plant Physiology).

Alunos de Ciências

Uma iniciativa gratuita, dirigida aos estudantes do 1.º Ciclo de estudos de Ciências ULisboa.

Título/data/local do evento, logótipo da RedeMov e fotografia de autocarro

Evento no âmbito do Ciclo de Conferências "Conversas à 6.ª", promovido pela redeMOV da Universidade de Lisboa.

Logótipo do programa e pormenor de comboio

Pronto para embarcar numa mobilidade sustentável e numa aventura multicultural?

Geometry and Physics Seminar / Theory of Computing Seminar por Florian Pausinger (Queen's University Belfast).

Título do evento e representação de rosto humano

An interdisciplinary workshop that brings together world-leading scholars, junior researchers, artists, clinicians and more importantly people with lived experiences of Depersonalisation to address key questions around this widely spread yet under-acknowledged condition.

Composição do logótipo da ULisboa e de representação do rosto humano à base de relógios

Consegue comunicar eficazmente a sua investigação de doutoramento em 3 minutos?

Ao longo das 30 horas deste curso, serão abordados temas, tais como contornar as principais dificuldades na comunicação da Biodiversidade, como usar histórias, ou a importância dos conceitos científicos na hora de os comunicar.

Título/data/local do evento

O evento visa mobilizar atores nacionais nas missões europeias do Horizonte Europa que contribuem para o Pacto Ecológico Europeu.

Pormenor da exposição e data da visita guiada

Visita guiada pela autora da exposição, Inez Wijnhorst, e o seu curador, Pedro Freitas (CIUHCT), apresentando duas visões - a artística e a matemática - que se complementam.

Fotografia de participantes numa anterior edição da Jobshop Ciências

O maior evento de empregabilidade de Ciências, a decorrer nos dias 09 e 10 de abril.

Título do programa, sobre um fundo azul escuro

Candidaturas até 31 de março.

Título do evento e mosaico de imagens (feixe de luz e silhueta humana)

Estás pronto para alavancar o teu conhecimento e abrir novas oportunidades profissionais?

Título/data/local do evento

An advanced worshop organised by 3D-BioInfo-PT, the community of Portuguese scientific researchers working in fields connected to Structural Bioinformatics.

The conference aims to bring together students and young researchers working in Mathematics, Statistics, and Applications with a view to fostering discussions and collaborations amongst participants.

Logótipos do Concurso Nacional para Jovens Cientistas e Investigadores e da Fundação da Juventude

Candidaturas até 15 de abril.

Seminário Helena Avelar de Astronomia e Astrologia Antiga, por Levente László (Eötvös University).

Logótipo de Ciências ULisboa, título "Dia de Ciências 2024" e frase apelando à participação

23 de abril. Virgínia Dignum, especialista Nações Unidas para IA, é oradora convidada.

O encontro reúne cientistas, profissionais e estudantes de diferentes áreas e regiões do país focados em desenvolver a investigação marinha, em linha com a Década da Ciência Oceânica para o Desenvolvimento Sustentável, proclamada pelas Nações Unidas (2021-2030).

Logótipo da ação CLEANFOREST

Forests are exposed to multiple global change drivers, wich can constrain their ability to continue providing several ecosystem services (including climate change mitigation). Assessing responses - and underlined mechanisms -  at the whole ecosystem scale is paramount for a holistic understanding of forest response to global change.

Título e data do evento, inseridos em fotografia de cinco jovens em contexto de investigação

Pré-inscrições já disponíveis!

Título do curso

Curso Avançado CEAUL / Gades Solutions.

Logótipo do EVM 2024

Candidaturas até 15 de maio.

Páginas