Como / Por que os sistemas lineares são tão cruciais para a ciência da computação?

9

Comecei a me envolver com a otimização matemática recentemente e estou adorando. Parece que muitos problemas de otimização podem ser facilmente expressos e resolvidos como programas lineares (por exemplo, fluxos de rede, cobertura de borda / vértice, vendedor ambulante etc.). Sei que alguns deles são difíceis de NP, mas o ponto é que eles podem ser 'enquadrado como um programa linear' se não for resolvido da melhor maneira.

Isso me fez pensar: sempre aprendemos sistemas de equações lineares, álgebra linear em toda a escola / faculdade. E ver o poder dos LPs em expressar vários algoritmos é meio fascinante.

Pergunta: Embora tenhamos sistemas não lineares predominantes ao nosso redor, como / por que os sistemas lineares são tão cruciais para a ciência da computação? Entendo que eles ajudam a simplificar o entendimento e são tratáveis ​​computacionalmente na maioria das vezes, mas é isso? Quão boa é essa 'aproximação'? Estamos simplificando demais e os resultados ainda são significativos na prática? Ou é apenas "natureza", ou seja, os problemas mais fascinantes são de fato simplesmente lineares?

Seria seguro que 'álgebra linear / equações / programação' sejam as pedras angulares do CS? Se não, então o que seria uma boa contradição? Quantas vezes lidamos com coisas não lineares (eu não necessariamente quero dizer teoricamente, mas também do ponto de vista da 'solvabilidade', ou seja, apenas dizer que o NP não é suficiente; deve haver uma boa aproximação ao problema e ele chegaria sendo linear?)

Doutorado
fonte
4
Não diminuí o voto, mas não vejo por que a tratabilidade não é uma resposta satisfatória para você. Existem alguns sentidos precisos interessantes nos quais problemas não convexos são intratáveis, por exemplo. arxiv.org/abs/1210.0420 .
Colin McQuillan
2
Os que recusam podem ter muitas razões pelas quais optam por não comentar.
Tyson Williams
11
Uma maneira de ver isso é que qualquer problema de NP pode ser reduzido à programação inteira em tempo polinomial e, em seguida, o problema de programação inteira pode ser relaxado. mas usamos técnicas espectrais e relaxações de SDP, que são problemas de otimização quadrática que são eficientemente solucionáveis.
Sasho Nikolov 18/10/12
11
O que significa "sistemas lineares" nesta pergunta?
Tsuyoshi Ito
11
sistemas lineares são encontrados em todo o período científico ... é uma simplificação que obtém uma milhagem surpreendentemente alta ... parece um pequeno corolário da eficácia irracional da matemática nas ciências naturais .. aparentemente, o CS se encaixa nessa categoria de "ciências naturais "... está intimamente aliado à física, sem dúvida cada vez mais [por exemplo, transistores encolhendo, dissipação de calor, QM de baixo nível, estudo do consumo de energia, entropia, etc.] ...
vzn

Respostas:

12

A premissa da pergunta é um pouco falha: muitos argumentam que os quadráticos são o verdadeiro "limite" para tratabilidade e modelagem, uma vez que os problemas dos mínimos quadrados são quase tão "fáceis" quanto os problemas lineares. Outros argumentam que a convexidade (ou mesmo submodularidade em certos casos) é o limite para a tratabilidade.

f(x+y)=f(x)+f(y)

Essa falta de memória confere eficiência: eu posso quebrar as coisas em pedaços ou trabalhar iterativamente, e não perco em virtude disso. Ainda posso tomar más decisões (cf. algoritmos gananciosos), mas o ato de dividir as coisas em si não me machuca.

Essa é uma das razões pelas quais a linearidade tem esse poder. Provavelmente existem muitos outros.

Suresh Venkat
fonte
Eu gosto desta resposta, mas para aqueles que argumentam que a programação linear não é o limite, respondo com: "é P-complete!" ;).
Artem Kaznatcheev
Sim, mas será que (por exemplo) os SDPs não são?
Suresh Venkat
Não precisamos ter um único limite, e alguns limites de P (digamos, programação quadrática com matriz semi-definida positiva para os termos ao quadrado) parecem mais gerais. Eu não quis discordar, estava apenas apontando que o limite é mais uma questão de gosto ao escolher entre problemas com P completo.
Artem Kaznatcheev
5

" Embora tenhamos sistemas não lineares predominantes ao nosso redor, como / por que os sistemas lineares são tão cruciais para a ciência da computação?"

Aqui está uma resposta parcial em minha mente: Eu acho que é porque a natureza é abundante em objetos / fenômenos - representáveis ​​por funções que, embora não lineares em seus operandos, são na verdade membros de espaços lineares. A onda funciona em um espaço de Hilbert, os componentes em um espectro de quatro camadas, anéis polinomiais, processos estocásticos - todos se comportam dessa maneira. Até definições muito gerais de espaços curvos são construídas para compor pequenos gráficos de espaços planos (variedades, superfícies de Riemann, ..). Além disso, a natureza é cheia de simetrias e o estudo de simetrias invariavelmente entra em estudo de operadores lineares (a teoria da representação, em minha opinião, está se infiltrando em muitas áreas da ciência da computação de maneira tão onipresente).

Isso ocorre além dos casos em que os próprios operadores são de natureza linear.

Uma grande fração dos problemas para os quais precisamos de programas de computador surge diretamente como ou é abstraída de fenômenos que ocorrem naturalmente. Talvez estudar / resolver sistemas lineares não deva ser uma grande surpresa, afinal?

Arnab
fonte
Ah, sim, as maravilhosas alegrias de levantar mapas.
Suresh Venkat