构造性 P=NP 证明的现实应用
原文:https://www . geesforgeks . org/real-world-applications-of-a-construction-PNP-proof/
先决条件:NP-完全性
构造性 P=NP 证明的现实应用: 多项式类问题，也称为 P，在多项式时间内是可解的。然而，另一类问题在多项式时间内是不可解的，但其解可以很快得到验证。这些被称为非多项式可解的确定性问题。
P 与 NP 问题是计算机科学领域中一个尚未解决的主要问题。目前的假设是 P！=NP，因为反过来意味着在识别问题并获得相应的解决方案时没有根本的差距。然而，许多科学家认为，这个课题正处于空间算法需要更多探索的阶段，并且将获得 P = NP 的明确解。这意味着一个问题的解决方案可以在多项式时间内找到并验证。
P = NP 问题的构造性证明将意味着通过指定的合理界限、边界多项式和算法及其功能的详细描述来识别解。
NP 完全问题包含了广泛的应用，因此，P = NP 证明的实际应用既可以是正的，也可以是负的。如果
，那么我们将能够以更高的效率解决大量的决策、搜索、计数、采样以及优化问题。建设性证明的发展意味着几乎所有的 NP 问题都可以在多项式时间内确定性地解决。它将为大量具体问题提供 应用和答案，如设计更好的桥梁，或找到更好的药物，也为大量科学理论或“自然法则”提供补救。 这会改变工程问题的动态。
W e 本可以有一些更大的现实世界的应用相同:
- 素因子分解算法– 因为大量密码算法，例如 RSA，将易于开发和计算。即使密钥很小，RSA 加密也很容易理解。
- 【车辆路径(旅行推销员问题)– 交通部门占欧盟 GDP 的 10%。能够找到到城市之间任何可能的点对的最短路径，将使交付和旅行变得非常容易，并将节省大量资金。
- 设施位置– 可以找到工厂搬迁的最佳地点，在那里物资可以很容易地运送到商店。这将提高效率，同时减少工厂开支。
- 电路设计– 大型布尔电路基于近似求解。如果能有效地计算电路求解，就能大大减少对硬件的依赖。最小化很容易做到。
- 调度算法– 日常问题中出现的冲突，如决定考试日期、组织一些重要事件，很容易就能最小化。
- 机票预订– 距离造型是预订飞机或火车票时需要考虑的重要因素。如果 P = NP，那么就有可能找到游览城市时要遵循的最佳点序列。很容易有最便宜的航班序列，访问一些城市，在理想的城市结束。比如从 A - > B - > C，可能比直接达到 A - > C 更可行。
- 编译器– 大多数编译器在其架构中使用图着色进行寄存器分配。寄存器分配将得到优化，以包括大量用于存储的寄存器。现有的解决方案，例如弦图，提供了近似的解决方案，精确的解决方案在很大程度上意味着更快的处理。
- 图形优化– 一个独立的集合，3SAT，图形着色将导致它在广泛领域的应用。
- 计算机辅助设计和人工智能算法的设计和实现将变得更加容易。
- 蛋白质结构预测问题将很容易在多项式时间内解决，这将导致技术和科学的进步。
- 密码学–
开发一个 P = NP 问题的构造性证明，例如一个 3 SAT 问题，会破坏大量现有的密码系统:
- 公钥加密
- 对称密码
- 加密哈希，包括比特币系统
- 运筹学– 例如，针对该问题开发多项式有界算法将在很大程度上改善物流。
- 使用奥卡姆剃刀原理可以很容易地找到数学定理的逻辑证明和非常简短的证明。通过找到与数据一致的最小程序，这将进一步简化学习过程。
- 天气预报和预报将更加准确。
- 人工智能– 翻译将很容易完成，因为我们将从有限的一组输入中获得正确的输出。完美的语音识别可以轻松完成。
版权属于：月萌API www.moonapi.com，转载请注明出处
