Grande correlação com o problema do knapsack, leia antes
aqui, e se não gostou, não tente continuar a ler este.
No fundo este problema é muito menos importante e menos discutido do que o problema do knapsack, mas mesmo assim vale a pena dar uma olhada.
Segundo a Wikipedia: "Na teoria dos grafos, um conjunto independente de um grafo G é um conjunto S de vértices de G tal que não existem dois vértices adjacentes contidos em S. Em outras palavras, se a e b são vértices quaisquer de um conjunto independente, não há aresta entre a e b. [...] Se S é um conjunto independente de G e não existe um conjunto independente de G maior que S, diz-se que S é um conjunto independente máximo de G." Provavelmente você não entendeu a explicação nada simples acima, então resumindo o problema: o nome do problema é
conjunto independente máximo (maximum independent set problem) e se resume a um grafo, que é um monte de vértices e arestas juntos, um conjunto independente é aquele que não existem dois vértices "vizinhos" (compartilhando uma mesma aresta) no conjunto, e queremos escolher um conjunto independente tal que maximize seu tamanho. Na imagem acima, as bolinhas coloridas são os vértices, os traços pretos são as arestas, e representa 1 grafo e 6 modos diferentes de escolher conjuntos independentes (apenas os vermelhos) nesse grafo, e apenas 2 são soluções para este problema (tente descobrir quais são).
Este problema também é um problema NP-completo, igual o knapsack, e agora que você provavelmente entendeu os dois problemas, vai um fato curioso: existem 21 problemas nessa classificação, todos bastante diferentes assim como este em relação ao problema do knapsack, e mesmo assim, resolvendo um deles você automaticamente está resolvendo todos ao mesmo tempo.
Certo, e o que isso tem a ver com o Bitcoin ? É possível separar o problema em duas partes, ambos relacionados a incluir a transação no bloco:
1)
Conflito entre transações tentativas de gasto duplo: Se existem várias transações tentando usar o mesmo dinheiro dizemos que as transações estão conflitando entre si, e então criamos um grafo onde cada vértice é uma transação e cada aresta entre A e B quer dizer que A e B estão em conflito entre si. E então apenas resolvemos o problema descrito acima (maior conjunto = mais transações = quase_sempre_mais_dinheiro).
2)
Transações que dependem do saldo de uma outra transação não confirmada: Nesse caso o problema é de dependência, se a transação B usa o dinheiro da transação A, ambas não confirmadas, e eu quiser colocar a transação B no bloco, eu devo colocar a A obrigatoriamente. Colocar este problema junto com o item 1) em um grafo exige um pouco mais de teoria, mas acredite quando eu digo que este problema fica mais fácil se "incorporado" ao item 1) .
Então basicamente o problema com as transações agora é questão de bloco válido ou não, e não apenas uma questão de lucro adicional como tínhamos no problema do knapsack.
Certo, e como se resolve isso ? Um ponto muito importante nisso tudo é que devemos lembrar que transações de gasto duplo são extremamente raras (os nodes/carteiras já têm um sistema que impede de ficar recebendo/mandando um monte de transações de gasto duplo). E sobre as dependências entre transações temos que elas são mais simples de calcular se você não tiver o problema de conflito (gasto duplo), bastando que se a B depende da A o minerador trata a B como se fosse um "A+B" (bytes A + bytes B + fee A + fee B), o que na verdade faz com que o knapsack problem fique um pouco mais difícil, mas o algoritmo guloso simplesmente ignora isso.
Então diferentemente do problema do knapsack, onde os mineradores simplesmente faziam uma escolha simples que já rende um lucro próximo ao máximo, o maximum independent set problem pode ser simplesmente calculado com algum algoritmo lento, já que os números são muito baixos.
Conclusão Este é um problema NP-completo que os mineradores simplesmente não resolveram, simplesmente a ignoraram e mesmo assim temos a solução perfeita. Quem sabe se um dia o mesmo conseguirem fazer o mesmo em relação ao knapsack problem ?
parte um pouquinho mais técnica para os curiosos:
Eu acho que este post já possui informação demais pra ser absorvida, se quiser mais mesmo leia mais nos links abaixo.
Fontes:
https://pt.wikipedia.org/wiki/Conjunto_independentehttps://en.wikipedia.org/wiki/Maximal_independent_sethttps://freedom-to-tinker.com/2014/10/27/bitcoin-mining-is-np-hard/
