Saltar para o conteúdo

Ficheiro:3SAT-3COL reduction.svg

O conteúdo da página não é suportado noutras línguas.
Origem: Wikipédia, a enciclopédia livre.

Imagem numa resolução maior ‎(ficheiro SVG, de 720 × 522 píxeis, tamanho: 9 kB)

Descrição do ficheiro

Descrição
English: Gadgets for an NP-completeness proof of graph 3-coloring, by reduction from 3-Satisfiability. The variable and clause gadgets are shown on the upper and lower left, respectively, and the right side of the figure shows the complete reduction for the instance (x ∨ y ∨ ~z) ∧ (~x ∨ ~y ∨ z) with three variables and two clauses. This reduction is from Oded Goldreich, Computational Complexity: A Conceptual Perspective, Cambridge University Press, 2008, Proposition 2.27, p. 81.
Data
Origem Obra do próprio
Autor David Eppstein

Licenciamento

Eu, titular dos direitos de autor desta obra, publico-a com a seguinte licença:
Creative Commons CC-Zero A utilização deste ficheiro é regulada nos termos Creative Commons - CC0 1.0 Dedicação Universal ao Domínio Público.
A pessoa que associou uma obra a este documento dedicou-a ao domínio público, renunciando a todos os seus direitos sobre a obra em todo o mundo ao abrigo da legislação de direitos de autor, incluindo a todos os direitos legais conexos, na medida permitida por lei. Pode copiar, modificar, distribuir e executar a obra, até com fins comerciais, sem pedir autorização.

Legendas

Adicione uma explicação de uma linha do que este ficheiro representa

Elementos retratados neste ficheiro

retrata

tipo de média

image/svg+xml

soma de verificação

ea8a94ebcc4964b3b08af05b56f2b45575514be6

método de determinação: SHA-1

altura

522 pixel

largura

720 pixel

Histórico do ficheiro

Clique uma data e hora para ver o ficheiro tal como ele se encontrava nessa altura.

Data e horaMiniaturaDimensõesUtilizadorComentário
atual22h41min de 27 de fevereiro de 2012Miniatura da versão das 22h41min de 27 de fevereiro de 2012720 × 522 (9 kB)David Eppstein{{Information |Description ={{en|1=Gadgets for an NP-completeness proof of graph 3-coloring, by reduction from 3-Satisfiability. The variable and clause gadgets are shown o...

A seguinte página usa este ficheiro:

Utilização global do ficheiro

As seguintes wikis usam este ficheiro:

Obtida de "https://pt.wikipedia.org/wiki/Ficheiro:3SAT-3COL_reduction.svg"