Os problemas estudados no ProComb ocupam um lugar de destaque dentro dos temas pesquisados em Teoria da Computação nos principais centros de pesquisa mundiais.
É importante que sejam mencionadas as relações de cooperação dos participantes do projeto com pesquisadores de tais centros, tais como o laboratório LSDD de Grenoble, laboratório LACIM da UQAM de Montreal, departamento de combinatória e otimização da Universidade de Waterloo, Konrad-Zuse-Zentrum für Informationstechnik de Berlim, Universidade de Montreal, departamento de matemática da Universidade de Cambridge, departamento de matemática e ciência da computação da Emory University, Instituto de Matemática da Adam Mickiewicz University (Poznan, Polônia), Instituto de Matemática da Academia Polonesa de Ciências, Institut für Ökonometrie und Operations Research der Universität Bonn, entre outros.
A contribuição mais relevante do ProComb talvez seja a integração dos centros de pesquisa do Rio de Janeiro e São Paulo, que possuem grupos com interesses comuns, tais como teoria dos grafos e otimização. Este intercâmbio, contribuirá para a uniformização e difusão de linguagem técnica na área, no idioma Português.
O estudo de problemas estruturais e algorítmicos em grafos, contemplado no Problema 1, é de grande interesse em Teoria da Computação. Os grafos perfeitos, por exemplo, surgiram há mais de 30 anos, motivados por diversas aplicações algorítmicas e práticas. Outro exemplo que mostra a importância desta pesquisa, à primeira vista puramente teórica, são os grafos de intervalo. Esses grafos podem ser utilizados para modelar problemas que surgem nas mais variadas áreas do conhecimento, tais como seqüenciamento de DNA, estudo de árvores filogenéticas e projetos de circuitos VLSI.
Embora de interesse puramente teórico, e centrado num problema que despertou pouca atenção nos últimos anos, o estudo das Equações de Birkhoff-Lewis proposto neste projeto deve ganhar novo impulso pelas conexões recentemente reveladas entre alguns aspectos desse problema: a presença dos polinômios de Behara, uma forma dos polinômios de Tchebyshev, revelada em [17, 76], também foi detectada em outras áreas [67]. A conexão natural dessas equações com os polinômios cromáticos também motiva nosso estudo, dada a intensa atividade que se desenvolve hoje na teoria de nós e os polinômios de Jones (veja por exemplo [41, 42, 43]).
Com relação aos Problemas 2 e 3, observamos que o desenvolvimento de algoritmos baseados em métodos poliedrais, métodos multi-algorítmicos, e métodos probabilísticos são de profundo interesse teórico e prático. A necessidade de solução de problemas de tamanho cada vez maiores impulsiona a busca de novas técnicas e estratégias. Os algoritmos aqui desenvolvidos têm potencial para serem utilizados na solução de problemas práticos do mundo real, como a literatura especializada nos mostra. Diversos trabalhos utilizaram métodos baseados nessas estratégias para resolver problemas de diversas áreas, tais como projeto de circuitos VLSI, projeto de redes de comunicação resistentes a falhas, classificação de dados, etc.