Se eu entendi corretamente, para provar que o problema é NP difícil, você precisa escolher todos os possíveis problemas que estão no NP e depois provar que eles se reduzem a usando uma função computável de tempo polinomial, que mapeia instâncias de cada a instâncias de
Alguém sabe de onde vêm os nomes Sistema "F" e Sistema "T"? Não estou perguntando quem apresentou esses nomes (Sistema Girard F e Sistema Gödel T), mas o que significa "F" e
O #P foi introduzido pela primeira vez em [1] ? [1] Valiant, Leslie G. "A complexidade de computar o permanente". Teoria da computação 8.2 (1979):
Nas duas perguntas a seguir, Origens e aplicações da teoria A vs teoria B? e Aplicações sólidas da teoria das categorias no TCS? , muitas pessoas compartilharam seus conhecimentos e opiniões sobre a divisão dessas duas áreas no CS teórico. Eu sou um estudante de matemática com experiência em...