Eu tenho um politopo definido por .
Pergunta: Dado um vértice de , existe um algoritmo de tempo polinomial para amostrar uniformemente os vizinhos de no gráfico de ? (Polinômio na dimensão, o número de equações e a representação de . Posso assumir que o número de equações é polinomial na dimensão.)
Atualização: acho que consegui mostrar que isso é difícil para o NP; veja minha resposta que explica o argumento. (E por -Hard, quero dizer que um algoritmo de tempo polinomial provaria ... não sei o que a terminologia correta é aqui.)
Update 2: Não é uma prova de 2 linhas de -hardness (dada a polytope combinatória direita) e eu era capaz de encontrá-lo um artigo de Khachiyan. Veja a resposta para descrição e link. :-D
Um problema equivalente :
Nos comentários, Peter Shor apontou que essa pergunta é equivalente à questão de saber se podemos amostrar uniformemente a partir dos vértices de um dado polítopo. (Eu acho que a equivalência é assim: em uma direção, podemos ir de um polítopo com um vértice para a figura do vértice em , , e amostrar os vértices de é equivalente a amostrar os vizinhos de em Na outra direção, podemos ir de um polítopo a um polítopo de uma dimensão superior, adicionando um cone com vértice e base . Então amostrar os vizinhos de em é equivalente a amostrar os vértices de )
Esta formulação da pergunta já foi feita antes: /mathpro/319930/sampling-uniformly-from-the-vertices-of-a-polytope
Respostas:
Editar 2: Embaraçosamente, existe uma prova duas linhas doNP -hardness, se se começar com o poliepítopo direita.
Primeiro, lembre-se de que o polítopo de circulação de um gráfico na parte inferior da página 4 de Gerar todos os vértices de um poliedro é difícil .
Seus vértices estão em correspondência bijetiva com os ciclos simples direcionados. Portanto, eles são difíceis de amostrar ou contar pela Proposição 5.1 da JVV . :-D
Equipado com essas palavras-chave, pude encontrar a dureza do resultado da amostragem como teorema 1 dos Higrógrafos Transversais e Famílias de Cones Poliédricos de Khachiyan .
Edit: Eu escrevi o argumento abaixo, e parece correto. No entanto, há um argumento muito mais simples, que descreverei aqui:
a) Pela análise dos algoritmos de backtrack para listar todos os vértices e todas as faces de um poliedro convexo (Fukuda et al.), é altamente NP difícil resolver o seguinte problema nos politopos:
Entrada: Um polítopoAx=b,x≥0 no Rn um subconjunto S⊆n
Saída: Se há um vérticev de P que é diferente de zero em cada uma das coordenadas em S .
b) Dado isso, pode-se fazer a seguinte construção: introduzir novas variáveisyik para i∈S e k=1,…,d , e introduzir a desigualdade 0≤yik≤xi . Chame o polítopo resultantePS,d . O objetivo dessa construção é introduzir um hipercubo acima de cada vértice, da dimensãod|supp(x)∩S| .
c) Pode-se verificar se todos os vértices deste polítopo estão todos acima dos vértices do polítopo antigo e se o número de vértices sobre um vértice é2d|supp(x)∩S| , em que supp é a função que envia um vértice para as coordenadas em que é diferente de zero.
d) Por uma corrente usual de argumento do tipo bigons, segue-se que, tomandod suficientemente grande, uma amostra uniforme dos vértices de PS,d daria (com alta probabilidade) uma amostra dos vértices, maximizando o tamanho de sua interseção com S .
Parece haver várias extensões disso. Vou atualizar com um link quando a escrita estiver concluída.
(O argumento antigo costumava estar aqui - está no histórico de edições. Eu o removi porque é muito longo e interfere na localização da resposta correta para a pergunta.)
fonte