Existem classes de complexidade estabelecidas com números reais?

Recentemente, um aluno me pediu para verificar uma prova de dureza NP para eles. Eles realizaram uma redução ao longo das linhas de:

Reduzo esse problema $P'$ que é conhecido como NP-completo para o meu problema (com uma redução de múltiplos de um tempo múltiplo), de modo que é NP-difícil.$P$$P$

Minha resposta foi basicamente:

Como possui instâncias com valores de , não é trivialmente computável em Turing, portanto você pode pular a redução.$P$$\mathbb{R}$

Embora formalmente verdade, não acho que essa abordagem seja perspicaz: certamente gostaríamos de capturar a "complexidade inerente" de um problema de decisão (ou otimização) com valor real, ignorando as limitações que enfrentamos ao lidar com problemas reais. números; investigar esses problemas é para outro dia.

Obviamente, nem sempre é tão fácil quanto dizer: "a versão discreta do Subset Sum é NP-completa, portanto a versão contínua também é 'NP-hard'". Nesse caso, a redução é fácil, mas há casos famosos da versão contínua sendo mais fácil, por exemplo, programação linear versus número inteiro.

Ocorreu-me que o modelo de RAM naturalmente se estende a números reais; deixe cada registro armazenar um número real e estender as operações básicas de acordo. O modelo de custo uniforme ainda faz sentido - tanto quanto no caso discreto, de qualquer maneira - enquanto o modelo logarítmico não.

Portanto, minha pergunta se resume a: existem noções estabelecidas de complexidade de problemas com valor real? Como eles se relacionam com as classes discretas "padrão"?

^{As pesquisas do Google produzem alguns resultados, por exemplo, isso , mas não tenho como dizer o que é estabelecido e / ou útil e o que não é.}

Sim. Tem.

Existe o modelo de RAM / BSS real mencionado na outra resposta. O modelo tem alguns problemas e o AFAIK não possui muita atividade de pesquisa. Indiscutivelmente, não é um modelo realista de computação .

A noção mais ativa de computabilidade real é a do modelo de computação de tipo superior. A idéia básica é que você defina a complexidade para funções de tipo mais alto e use funções de tipo mais alto para representar números reais.

O estudo da complexidade das funções de tipo superior remonta a pelo menos 1. Para trabalhos recentes, verifique os documentos da Akitoshi Kawamura sobre a complexidade de operadores reais.

A referência clássica para a complexidade de funções reais é o livro de Ker-I Ko [2]. No sexto capítulo, o livro mais recente de Klause Weihrauch [3] também discute a complexidade da computação real (mas é mais focada na computabilidade do que na complexidade).

• [1] Stephen Cook e Bruce Kapron, "Caracterizações dos funcionais básicos viáveis ​​do tipo finito", 1990.

• [2] Ker-I Ko, "Complexidade computacional de funções reais", 1991.

• [3] Klaus Weihrauch '"Computable Analysis", 2000.

O modelo que você descreve é ​​conhecido como modelo Blum-Shub-Smale (BSS) (também modelo Real RAM) e, de fato, é usado para definir classes de complexidade.

Alguns problemas interessantes neste domínio são as classes , N P R , e, claro, a questão de saber se P R = N P R . Por P R queremos dizer o problema é polinomialmente decidíveis, N P R é o problema é polinomialmente verificável. Existem dureza / completude dúvidas sobre a classe N P R . Um exemplo de um problema completo N P R é o problema de Q P S , Sistema Polinomial Quadrático, em que a entrada é polinômio real em$P_R$$NP_R$$P_R$$NP_R$$P_R$$NP_R$$NP_R$$NP_R$$QPS$ variáveis, e p 1 , . . . , P n ⊆ R [ x 1 , . . . , x n ] de grau no máximo 2, e cada polinômio tem no máximo 3 variáveis. A questão de saber se existe uma verdadeira solução comum R n , de tal modo que p 1 ( uma ) , p 2 ( um ) , . . . p n ( a ) = $m$$p_1, ..., p_n$ $\subseteq$ $R[x_1, ..., x_n]$$R^n$$p_1(a), p_2(a), ... p_n(a) = 0$. Este é um problema completa.$NP_R$

$PCP$$PCP_R$$NP$$NP_R$$NP_R$ . Há também uma extensão que diz que a "Versão curta quase (aproximada)" também é verdadeira. Podemos estabilizar a prova e detectar falhas inspecionando consideravelmente menos componentes (reais) que n ? Isso leva a perguntas sobre a existência de zeros para (sistema de) polinômios univariados dados pelo programa em linha reta. Além disso, por "provas longas transparentes" queremos dizer$PCP_R(poly, O(1))$$n$

1. "transparente" - somente a ser lido,$O(1)$

2. número superpolinomial longo de componentes reais.

A prova está ligada a , e com certeza uma maneira de analisar problemas com valor real é como ela pode estar relacionada à Subconjunto - até mesmo algoritmos de aproximação para problemas com valor real seriam interessantes - como para otimização - Programação Linear que conhecemos está na classe F P , mas sim, seria interessante ver como approximatability pode afetar a integridade / dureza para o caso de N P R problemas. Além disso, outra pergunta seria a N P R = c o - N P R ? $3SAT$$FP$$NP_R$$NP_R$ $=$ $co\text{-}NP_R$

$NP_R$$\#P$$f$$\{0,1\}^\infty$ $\rightarrow$ $\mathbb{N}$$M$$p$$\forall n$$\in$$\mathbb{N}$$x$$\in$$\{0,1\}^{n}$$f(x)$$y \in$$\{0,1\}^{p(n)}$$M$$\{x,y\}$$\# P$$\#P_{add}$ essa classe é útil no estudo dos números de Betti e também da característica de Euler.