В какой области программирования больше всего задач класса NP?

Question

[abelisk]

В особенности интересуют направления исследовательского характера, при этом направления должны быть прикладными. Идти работать профессором не предлагайте, не из-за зарплаты, хочется потрогать их "ручками".

Второй вопрос, имеются ли направления полностью построенные на задачах данного класса?

Comments

[Василий Назаров]

похоже, вам имеет смысл идти сразу в ML

Answer 1

[sim3x]

Не ответ, а направление для исследования

Берете NP задачу и прямо в ее условии имеем область куда прикладывать

Задача коммивояжера / доставки / транспортная задача
Задача раскроя
...

Проблема в том, что в таких областях уже сидят компании с професорами, которые сделали продукты для бизнеса. И чтоб работать в етой нише вам не нужно знать математику, а нужно уметь пользоваться уже готовым продуктом

Comments

[x67]

Или идти в эти компании, разрабатывающие коммерческие мат. пакеты и прочие продукты

[sim3x]

x67: уборщиком?

Туда как раз без научной степени и не возьмут щупать ручками

[x67]

sim3x: А вы считаете, профессоры там занимаются всем, начиная написания алгоритма на бумаге, заканчивая встраиванием его в конечный продукт/линейку продуктов?

[sim3x]

x67:
кодингом занимаются их аспиранты и их ктн / кфм

Answer 2

[chupasaurus]

Хочется потрогать - трогайте сами любую из списка, какая понравится. Важные свойства задач из множества NP-полных - решение одной задачи можно переложить на любую другую задачу из класса, а соответственно и на все NP-трудные (но для них они будут далеки от оптимальных).

Answer 3

[Philipp]

Напишите фреймворк для решения задач NP-класса.
Например ну очень часто встречается задача упаковки товаров в коробки, укладки их в грузовик и их отгрузки наиболее дешевым способом. В такого рода задачах есть набор ограничений (например тяжелые коробки нельзя ставить сверху, некоторые коробки нельзя переворачивать, на хрупкие вещи ничего нельзя ставить сверху). Мегазадача. Очень нужная на практике.
Напишите библиотеку на PHP или npm-пакетик. Opensource разумеется. Отличный пример - модуль для OpenCart.
В итоге получите 3 вещи: реальный опыт, коммьюнити (вещь востребованная), работу. Но прийдется попотеть, задача ведь NP-трудная.