当前位置: 首页 > 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;前言 小伙伴们大家好…...

网络六边形受到攻击

大家读完觉得有帮助记得关注和点赞&#xff01;&#xff01;&#xff01; 抽象 现代智能交通系统 &#xff08;ITS&#xff09; 的一个关键要求是能够以安全、可靠和匿名的方式从互联车辆和移动设备收集地理参考数据。Nexagon 协议建立在 IETF 定位器/ID 分离协议 &#xff08;…...

MPNet:旋转机械轻量化故障诊断模型详解python代码复现

目录 一、问题背景与挑战 二、MPNet核心架构 2.1 多分支特征融合模块(MBFM) 2.2 残差注意力金字塔模块(RAPM) 2.2.1 空间金字塔注意力(SPA) 2.2.2 金字塔残差块(PRBlock) 2.3 分类器设计 三、关键技术突破 3.1 多尺度特征融合 3.2 轻量化设计策略 3.3 抗噪声…...

SkyWalking 10.2.0 SWCK 配置过程

SkyWalking 10.2.0 & SWCK 配置过程 skywalking oap-server & ui 使用Docker安装在K8S集群以外&#xff0c;K8S集群中的微服务使用initContainer按命名空间将skywalking-java-agent注入到业务容器中。 SWCK有整套的解决方案&#xff0c;全安装在K8S群集中。 具体可参…...

Linux 文件类型,目录与路径,文件与目录管理

文件类型 后面的字符表示文件类型标志 普通文件&#xff1a;-&#xff08;纯文本文件&#xff0c;二进制文件&#xff0c;数据格式文件&#xff09; 如文本文件、图片、程序文件等。 目录文件&#xff1a;d&#xff08;directory&#xff09; 用来存放其他文件或子目录。 设备…...

CTF show Web 红包题第六弹

提示 1.不是SQL注入 2.需要找关键源码 思路 进入页面发现是一个登录框&#xff0c;很难让人不联想到SQL注入&#xff0c;但提示都说了不是SQL注入&#xff0c;所以就不往这方面想了 ​ 先查看一下网页源码&#xff0c;发现一段JavaScript代码&#xff0c;有一个关键类ctfs…...

微软PowerBI考试 PL300-选择 Power BI 模型框架【附练习数据】

微软PowerBI考试 PL300-选择 Power BI 模型框架 20 多年来&#xff0c;Microsoft 持续对企业商业智能 (BI) 进行大量投资。 Azure Analysis Services (AAS) 和 SQL Server Analysis Services (SSAS) 基于无数企业使用的成熟的 BI 数据建模技术。 同样的技术也是 Power BI 数据…...

3.3.1_1 检错编码(奇偶校验码)

从这节课开始&#xff0c;我们会探讨数据链路层的差错控制功能&#xff0c;差错控制功能的主要目标是要发现并且解决一个帧内部的位错误&#xff0c;我们需要使用特殊的编码技术去发现帧内部的位错误&#xff0c;当我们发现位错误之后&#xff0c;通常来说有两种解决方案。第一…...

1688商品列表API与其他数据源的对接思路

将1688商品列表API与其他数据源对接时&#xff0c;需结合业务场景设计数据流转链路&#xff0c;重点关注数据格式兼容性、接口调用频率控制及数据一致性维护。以下是具体对接思路及关键技术点&#xff1a; 一、核心对接场景与目标 商品数据同步 场景&#xff1a;将1688商品信息…...

JVM垃圾回收机制全解析

Java虚拟机&#xff08;JVM&#xff09;中的垃圾收集器&#xff08;Garbage Collector&#xff0c;简称GC&#xff09;是用于自动管理内存的机制。它负责识别和清除不再被程序使用的对象&#xff0c;从而释放内存空间&#xff0c;避免内存泄漏和内存溢出等问题。垃圾收集器在Ja…...

linux 下常用变更-8

1、删除普通用户 查询用户初始UID和GIDls -l /home/ ###家目录中查看UID cat /etc/group ###此文件查看GID删除用户1.编辑文件 /etc/passwd 找到对应的行&#xff0c;YW343:x:0:0::/home/YW343:/bin/bash 2.将标红的位置修改为用户对应初始UID和GID&#xff1a; YW3…...