当前位置: 首页 > news >正文

【算法】复杂性理论初步

六、算法复杂性初步


重要的复杂性类

  • P P P 的定义

    • 多项式时间内可解的问题

    • L ∈ P L∈P LP,则存在确定性多项式时间的图灵机 M M M,使得
      M ( x ) = 1 ⟺ x ∈ L M(x)=1⟺x∈L M(x)=1xL

  • N P NP NP 的定义

    • 多项式时间内可验证验证解的正确性

    • (表示非确定性多项式时间而不是非多项式时间)

    • L ∈ N P L∈NP LNP,则存在确定性多项式时间的图灵机 M M M,使得
      x ∈ L ⟺ ∃ w ∈ { 0 , 1 } p l o y ( n ) s . t . M ( x , w ) = 1 x∈L⟺\exist w∈\{0,1\}^{ploy(n)}\ \ s.t.\ M(x,w)=1 xLw{0,1}ploy(n)  s.t. M(x,w)=1
      注:如果 x ∈ L x∈L xL,那么存在一个证书 w w w,使 M M M能够在多项式时间内验证 x ∈ M x∈M xM

  • N P − h a r d NP-hard NPhard

    • 若一个问题属于 N P − h a r d NP-hard NPhard,那么它可以在多项式时间内规约成 N P NP NP 问题
  • N P − c o m p l e t e NP-complete NPcomplete

    • N P NP NP N P − h a r d NP-hard NPhard的交集,即 N P C = N P ∩ N P H NPC=NP∩NPH NPC=NPNPH
    • N P C NPC NPC N P NP NP中最难的问题,如果找到多项式时间解决 N P C NPC NPC,那么 P = N P P=NP P=NP

image-20241229184701985


SAT 问题

定义:给定一个布尔逻辑表达式,判断是否存在一个布尔变量赋值,使得整个表达式的值为真。

合取范式(CNF):一种布尔逻辑表达式的标准化形式,若干个句子合取(AND),每个句子中若干个文字析取(OR)

例如,以下一个CNF公式:
( ¬ a 1 ∨ a 2 ) ∧ ( ¬ a 1 ∨ a 3 ∨ a 4 ) ∧ ( a 1 ∨ ¬ a 2 ∨ a 3 ∨ ¬ a 4 ) (\neg a_1 \lor a_2) \land (\neg a_1 \lor a_3 \lor a_4) \land (a_1 \lor \neg a_2 \lor a_3 \lor \neg a_4) (¬a1a2)(¬a1a3a4)(a1¬a2a3¬a4)
注:存在一种赋值,使其中一个句子为真,整个CNF即为真。

2-SAT问题:每个子句恰好包含2个文字。 P P P 类问题。

3-SAT问题:每个子句恰好包含3个文字。 N P − c o m p l e t e NP-complete NPcomplete 问题。

  • 例如: ( l 1 ∨ l 2 ∨ l 3 ) ∧ ( l 4 ∨ l 5 ∨ l 6 ) ∧ ⋯ (l_1 \lor l_2 \lor l_3) \land (l_4 \lor l_5 \lor l_6) \land \cdots (l1l2l3)(l4l5l6)

当n>2,n-SAT问题就是NP-hard的。任何n-SAT都可以通过引入新变量的方法转化为3-SAT问题。


随机化算法

ZPP类型

  • 保证一定能找到正确答案
  • 需要多次运行,可以在期望的多项式时间内找到结果
  • 即:保证正确性,运行时间随机性
  • 如:随机化快速排序、随机化选择算法

BPP类型

  • 不保证得到正确答案,结果可能出错
  • 时间是确定的多项式时间
  • 即:时间复杂度好,结果不好
  • 如:矩阵恒等式测试

6.1 证明: P ⊆ N P P⊆NP PNP

证明

  • 对于 P P P问题的图灵机 M M M,构造另一个图灵机 M ′ M' M:输入是 w w w x x x,对于相同的 x x x有相同的输出, w w w对输出无影响
  • x ∈ L x∈L xL时, M ( x ) = 1 M(x)=1 M(x)=1,存在 w ′ ∈ 0 , 1 p l o y ( n ) w'∈{0,1}^{ploy(n)} w0,1ploy(n) M ′ ( x , w ′ ) = 1 M'(x,w')=1 M(x,w)=1
  • x ∉ L x ∉L x/L时, M ( x ) = 0 M(x)=0 M(x)=0,对于任意的 w w w M ′ ( x , w ) = 0 M'(x,w)=0 M(x,w)=0
  • 显然 M ′ M' M是确定性多项式图灵机,结合 N P NP NP问题定义,存在 w ′ ∈ 0 , 1 p l o y ( n ) w'∈{0,1}^{ploy(n)} w0,1ploy(n) M ′ ( x , w ′ ) = 1 M'(x,w')=1 M(x,w)=1,验证解是否正确。所以该 P P P问题也是一个 N P NP NP问题,所以 P ⊆ N P P⊆NP PNP

6.2 证明: 如果存在 N P NP NP 难的问题 Π ∈ P Π ∈ P ΠP,则 P = N P P = NP P=NP

证明

  • 根据 Π ∈ P Π ∈ P ΠP,得 Π Π Π在多项式时间可解决
  • 根据 N P − h a r d NP-hard NPhard 定义,所有 N P NP NP问题 F F F可在多项式时间内规约到 Π Π Π,即 F ∈ N P F∈NP FNP,有 F ≤ p Π F≤_pΠ FpΠ
  • 所以 F F F在多项式时间转化为 Π Π Π,再多项式求解 Π Π Π,整个过程是多项式时间完成的,所以 N P ⊆ P NP⊆P NPP
  • 又已知 P ⊆ N P P⊆NP PNP,所以证得 P = N P P=NP P=NP

6.3 证明:如果 N P = P NP=P NP=P,则单向陷门不存在。

  • 假设算法Invert用来寻找函数 f f f的逆映射:利用一系列语言 L i Li Li,表示是否存在 w w w使得 y = f ( z ∣ ∣ w ) y=f(z||w) y=f(z∣∣w)
  • 根据文本内容, L i Li Li属于 N P NP NP,同依据条件,也属于 P P P
  • 如果 P = N P P=NP P=NP,那么该算法能在多项式内求解,即找到了函数 f f f的逆映射,也就是找到 x x x使得 f ( x ) = y f(x)=y f(x)=y
  • 综上,若 N = N P N=NP N=NP,多项式时间可破坏单项函数的不可逆的性质,则单向陷门不存在

相关文章:

【算法】复杂性理论初步

六、算法复杂性初步 重要的复杂性类 P P P 的定义 多项式时间内可解的问题 若 L ∈ P L∈P L∈P,则存在确定性多项式时间的图灵机 M M M,使得 M ( x ) 1 ⟺ x ∈ L M(x)1⟺x∈L M(x)1⟺x∈L N P NP NP 的定义 多项式时间内可验证验证解的正确性 &…...

HarmonyOS NEXT应用开发实战:免费练手的网络API接口分享

学习一项技能,最好也最快的办法就是直接动手实战。在实战中不断的总结经验和收获成就感。这里分享些好用且免费的网络API练手接口,这对于想要提升自己网络开发能力的开发者来说,无疑是极大的福音。今天,我将详细介绍一个API接口集…...

C++的第一个程序

前言 在学习c之前&#xff0c;你一定还记得c语言的第一个程序 当时刚刚开始进行语言学习 因此告诉到&#xff0c;仅仅需要记住就可以 #include <stdio.h>int main(){printf("Hello World");return 0; }而对于c中的第一个程序&#xff0c;似乎有所变化 C的…...

Java 中 Stream 流的使用详解

Java 中 Stream 流的使用详解 什么是 Stream&#xff1f; Stream 是 Java 8 引入的一种全新的操作集合的方式。它支持通过声明性方式对集合进行复杂的数据操作&#xff08;如过滤、排序、聚合等&#xff09;&#xff0c;避免使用大量的 for 循环&#xff0c;提高代码的可读性…...

【UE5.3.2】生成vs工程并rider打开

Rider是跨平台的,UE也是,当前现在windows上测试首先安装ue5.3.2 会自动有右键的菜单: windows上,右键,生成vs工程 生成的结果 sln默认是vs打开的,我的是vs2022,可以open with 选择 rider :Rider 会弹出 RiderLink是什么插...

ssh免密码登陆配置

ssh 命令本身不支持直接在命令中带上密码&#xff0c;出于安全考虑&#xff0c;SSH 协议不允许将密码明文写在命令中。直接在命令行中输入密码是一种不推荐的做法&#xff0c;因为它会暴露密码&#xff0c;增加安全风险。 如果你希望实现自动化登录而不手动输入密码&#xff0…...

Hive之import和export使用详解

在hive-0.8.0后引入了import/export命令。 Export命令可以导出一张表或分区的数据和元数据信息到一个输出位置&#xff0c;并且导出数据可以被移动到另一个hadoop集群或hive实例&#xff0c;并且可以通过import命令导入数据。 当导出一个分区表&#xff0c;原始数据可能在hdf…...

数据库锁的深入探讨

数据库锁&#xff08;Database Lock&#xff09;是多用户环境中用于保证数据一致性和隔离性的机制。随着数据库系统的发展&#xff0c;特别是在高并发的场景下&#xff0c;锁的机制变得尤为重要。通过使用锁&#xff0c;数据库能够防止并发操作导致的数据冲突或不一致。本文将深…...

【每日学点鸿蒙知识】沉浸式状态栏、类似ref 属性功能属性实现、自定义对话框背景透明、RichEditor粘贴回调、自动滚动列表

1、HarmonyOS 沉浸式状态栏&#xff1f; 实现沉浸式状态栏功能时&#xff0c;能够实现&#xff0c;但是目前每个自定义组件都需要padding top 状态栏的高度才行&#xff0c;有办法实现统一设置吗&#xff1f;不需要每个自定义组件中都padding top 状态栏的高度&#xff1f; 暂…...

Hive刷分区MSCK

一、MSCK刷分区 我们平时通常是通过alter table add partition方式增加Hive的分区的&#xff0c;但有时候会通过HDFS put/cp命令或flink、flum程序往表目录下拷贝分区目录&#xff0c;如果目录多&#xff0c;需要执行多条alter语句&#xff0c;非常麻烦。Hive提供了一个"…...

在Ubuntu下通过Docker部署Mastodon服务器

嘿&#xff0c;朋友们&#xff0c;今天咱们来聊聊如何在Ubuntu上通过Docker部署Mastodon服务器。想要拥有自己的社交媒体平台&#xff1f;Mastodon就是个不错的选择&#xff01;&#x1f310;&#x1f680; Docker与Mastodon简介 Docker是一个开源的容器化平台&#xff0c;让…...

【EtherCATBasics】- KRTS C++示例精讲(2)

EtherCATBasics示例讲解 目录 EtherCATBasics示例讲解结构说明代码讲解 项目打开请查看【BaseFunction精讲】。 结构说明 EtherCATBasics&#xff1a;应用层程序&#xff0c;主要用于人机交互、数据显示、内核层数据交互等&#xff1b; EtherCATBasics.h &#xff1a; 数据定义…...

MYSQL无法被连接问题

如果您在尝试连接到MySQL服务器时遇到问题&#xff0c;以下描述了您可以采取的一些措施来纠正该问题。 确保服务器正在运行。如果没有&#xff0c;则客户端无法连接到它。例如&#xff0c;如果尝试连接到服务器失败并出现以下消息之一&#xff0c;则可能是服务器未运行&#xf…...

【Python】什么是字典(Dictionary)?

什么是字典&#xff08;Dictionary&#xff09;&#xff1f; 字典&#xff08;Dictionary&#xff09;是 Python 中一种 可变&#xff08;mutable&#xff09;的数据结构&#xff0c;用于存储键值对&#xff08;key-value pairs&#xff09;。字典通过 键&#xff08;key&…...

Web安全 - API 成批分配漏洞的四种修复方案

文章目录 概述危害修复建议与实施方案解决方案 1&#xff1a;手动绑定数据解决方案 2&#xff1a;使用 DTO 进行数据过滤解决方案 3&#xff1a;启用字段白名单解决方案 4&#xff1a;验证输入数据模式 验证修复有效性小结 概述 批量分配漏洞&#xff08;Mass Assignment&#…...

计算机网络实验室建设方案

一、计算机网络实验室拓扑结构 计算机网络综合实验室解决方案&#xff0c;是面向高校网络相关专业开展教学实训的综合实训基地解决方案。教学实训系统采用 B&#xff0f;S架构&#xff0c;通过公有云教学实训平台在线学习模式&#xff0c;轻松实现网络系统建设与运维技术的教学…...

ubuntu20.04 调试bcache源码

搭建单步调试bcache的环境&#xff0c;/dev/sdb作为backing dev&#xff0c; /dev/sdc作为cache dev。 一、宿主机环境 1&#xff09;安装ubuntu 20.04 &#xff1a; 参考ubuntu20.04 搭建kernel调试环境第一篇--安装系统_ubuntu kernel-CSDN博客安装&#xff0c;其中的第六…...

xss csrf怎么预防?

一、XSS&#xff08;跨站脚本攻击&#xff09;预防 XSS 是指攻击者向目标网站注入恶意脚本&#xff0c;从而在用户浏览器中执行。 1. 输入过滤 清理用户输入&#xff1a; 拦截或清理HTML特殊字符&#xff08;如 <, >, , ", &&#xff09;。使用安全库&#x…...

near-synonym反义词生成(2):Prompt +Bert-MLM(FT)

near-synonym之反义词生成方法二 near-synonym, 中文反义词/近义词/同义词(antonym/synonym)工具包. 方法一为(neg_antonym): Word2vec -> ANN -> NLI -> Length 方法二为(mlm_antonym): Prompt Bert-MLM(FT) Beam-Search 项目地址 github: https://github.com/yon…...

【服务器项目部署】⭐️将本地项目部署到服务器!

目录 &#x1f378;前言 &#x1f37b;一、服务器选择 &#x1f379; 二、服务器环境部署 2.1 java 环境部署 2.2 mysql 环境部署 &#x1f378;三、项目部署 3.1 静态页面调整 3.2 服务器端口开放 3.3 项目部署 ​ &#x1f379;四、测试 &#x1f378;前言 小伙伴们大家好…...

后进先出(LIFO)详解

LIFO 是 Last In, First Out 的缩写&#xff0c;中文译为后进先出。这是一种数据结构的工作原则&#xff0c;类似于一摞盘子或一叠书本&#xff1a; 最后放进去的元素最先出来 -想象往筒状容器里放盘子&#xff1a; &#xff08;1&#xff09;你放进的最后一个盘子&#xff08…...

边缘计算医疗风险自查APP开发方案

核心目标:在便携设备(智能手表/家用检测仪)部署轻量化疾病预测模型,实现低延迟、隐私安全的实时健康风险评估。 一、技术架构设计 #mermaid-svg-iuNaeeLK2YoFKfao {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg…...

Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility

Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility 1. 实验室环境1.1 实验室环境1.2 小测试 2. The Endor System2.1 部署应用2.2 检查现有策略 3. Cilium 策略实体3.1 创建 allow-all 网络策略3.2 在 Hubble CLI 中验证网络策略源3.3 …...

蓝牙 BLE 扫描面试题大全(2):进阶面试题与实战演练

前文覆盖了 BLE 扫描的基础概念与经典问题蓝牙 BLE 扫描面试题大全(1)&#xff1a;从基础到实战的深度解析-CSDN博客&#xff0c;但实际面试中&#xff0c;企业更关注候选人对复杂场景的应对能力&#xff08;如多设备并发扫描、低功耗与高发现率的平衡&#xff09;和前沿技术的…...

学习STC51单片机31(芯片为STC89C52RCRC)OLED显示屏1

每日一言 生活的美好&#xff0c;总是藏在那些你咬牙坚持的日子里。 硬件&#xff1a;OLED 以后要用到OLED的时候找到这个文件 OLED的设备地址 SSD1306"SSD" 是品牌缩写&#xff0c;"1306" 是产品编号。 驱动 OLED 屏幕的 IIC 总线数据传输格式 示意图 …...

NLP学习路线图(二十三):长短期记忆网络(LSTM)

在自然语言处理(NLP)领域,我们时刻面临着处理序列数据的核心挑战。无论是理解句子的结构、分析文本的情感,还是实现语言的翻译,都需要模型能够捕捉词语之间依时序产生的复杂依赖关系。传统的神经网络结构在处理这种序列依赖时显得力不从心,而循环神经网络(RNN) 曾被视为…...

【OSG学习笔记】Day 16: 骨骼动画与蒙皮(osgAnimation)

骨骼动画基础 骨骼动画是 3D 计算机图形中常用的技术&#xff0c;它通过以下两个主要组件实现角色动画。 骨骼系统 (Skeleton)&#xff1a;由层级结构的骨头组成&#xff0c;类似于人体骨骼蒙皮 (Mesh Skinning)&#xff1a;将模型网格顶点绑定到骨骼上&#xff0c;使骨骼移动…...

OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别

OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别 直接训练提示词嵌入向量的核心区别 您提到的代码: prompt_embedding = initial_embedding.clone().requires_grad_(True) optimizer = torch.optim.Adam([prompt_embedding...

稳定币的深度剖析与展望

一、引言 在当今数字化浪潮席卷全球的时代&#xff0c;加密货币作为一种新兴的金融现象&#xff0c;正以前所未有的速度改变着我们对传统货币和金融体系的认知。然而&#xff0c;加密货币市场的高度波动性却成为了其广泛应用和普及的一大障碍。在这样的背景下&#xff0c;稳定…...

Linux nano命令的基本使用

参考资料 GNU nanoを使いこなすnano基础 目录 一. 简介二. 文件打开2.1 普通方式打开文件2.2 只读方式打开文件 三. 文件查看3.1 打开文件时&#xff0c;显示行号3.2 翻页查看 四. 文件编辑4.1 Ctrl K 复制 和 Ctrl U 粘贴4.2 Alt/Esc U 撤回 五. 文件保存与退出5.1 Ctrl …...