Вероятностное тестирование NPC-сведения — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) (Новая страница: «В некоторых задачах сделано сведение NPC-задачи, обычно 3SAT, с иллюстрацией, но специально…») |
StasFomin (обсуждение | вклад) |
||
| Строка 4: | Строка 4: | ||
** PySAT | ** PySAT | ||
** Показанное сведение 3SAT → задача → Pyomo → ЦЛП-солвер. | ** Показанное сведение 3SAT → задача → Pyomo → ЦЛП-солвер. | ||
| − | ** Сверять | + | ** Сверять |
| + | *** если PySAT не нашел решения — то и вы не должны) | ||
| + | *** если нашел — то и у вас должно быть корректное решение. | ||
* В процессе можно найти ошибки в сведении, доработать и исправить его. | * В процессе можно найти ошибки в сведении, доработать и исправить его. | ||
Текущая версия на 12:30, 24 апреля 2023
В некоторых задачах сделано сведение NPC-задачи, обычно 3SAT, с иллюстрацией, но специально оставлена возможность доработки
- Сделать генерацию случайных 3SAT-формул (или можно специально сложных 3SAT-формул, из криптографии или еще откуда).
- Решать эти формулы параллельно через
- PySAT
- Показанное сведение 3SAT → задача → Pyomo → ЦЛП-солвер.
- Сверять
- если PySAT не нашел решения — то и вы не должны)
- если нашел — то и у вас должно быть корректное решение.
- В процессе можно найти ошибки в сведении, доработать и исправить его.