A Non-canonical Example to Support P Is Not Equal to NP

来源 :天津大学学报：英文版 | 被引量 : 0次 | 上传用户：llljjjxxx7

【摘要】

：

P 对 NP 问题和它的坚硬的判断的更不含糊的陈述，是发现 P 对 NP 问题的完整的证明的关键方法。处于 P 对 NP 问题有二亚问题。第一是不同数学问题(语言) 的分类，并且第二是在

【作者】

：

YANG Zhengling

【机构】

：

SchoolofElectricalEngineeringandAutomation,TianjinKeyLaboratoryofProcessMeasurementandControl

【出处】

：

天津大学学报：英文版

【发表日期】

：

2011年6期

【关键词】

：

NP问题不等 DTM NTM 数学问题非确定性图灵机子问题 P versus NP computational complexity theory

下载到本地 , 更方便阅读

下载此文赞助VIP

声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架

论文部分内容阅读

P 对 NP 问题和它的坚硬的判断的更不含糊的陈述，是发现 P 对 NP 问题的完整的证明的关键方法。处于 P 对 NP 问题有二亚问题。第一是不同数学问题(语言) 的分类，并且第二是在一台非确定的图灵机器(NTM ) 和一台确定的图灵机器(DTM ) 之间的区别。NTM 的过程能是相应 DTM 的一个力量集合，它证明 NTM 的状态能是相应 DTM 的一个力量集合。如果把这个观点与领唱者定理相结合， NTM 不对 DTM 同等，这被显示出。这意味着那产生集合 A 的力量集合 P (A) 是到 P 不等于

其他文献

Secrecy Performance of Untrusted Relay＇s Cooperation under Fading Channels

The secrecy performance of cooperation with an untrusted relay under a quasi-static fading channel is analyzed in this paper. An achievable secrecy rate is prov

期刊

保密性能衰落信道继电器合作仿真结果准静态中继信任physical layer security secrecy rate outage se

Scheduling of Household Power Consumption for Step and Time-of-Use Tariff System

这份报纸建议混合优化解决为步和 Time-of-Use (TOU ) 安排家庭电源消费关税系统。目标函数是电的费用，并且优化对象是在一个收费时期以内的全部的即时电源。控制变量正在开始

期刊

生活用电税制时间调度计算机模拟嵌入式应用混合优化电力成本smart grid scheduling optimization TOU ta

Blind Separation of Speech Signals Based on Wavelet Transform and Independent Component Analysis

在频率领域的讲话信号基于分离小浪变换(DWT ) 和独立部件分析(集成通信适配器) 被分开。首先，混合了讲话信号被 DWT 分解成不同频率域，讲话信号的 subbands 在每小浪域用集成

期刊

离散小波变换独立成分分析语音信号分离基ICA盲源分离采样速率DWTwavelet transform independent componen

Extended Mobile-Host-Centric Transport Protocol

In wireless networks, data packets are lost due to channel interference and fading rather than network congestion. Thus, TCP designed for wired networks, cannot

期刊

MCP多跳跃WLAN跨层拥挤控制MCP multi-hop WLAN cross-layer congestion control

Measuring In-Plane Micro-Motion of Micro-Structure Using Optical Flow

光流动方法是分析运动图象的最重要的方法之一。光流动地被用来分析运动目标的特征。根据微电子的机械系统(MEMS ) 的运动特征微观结构，光算法基于标签地和邻居优化被介绍分析

期刊

微电子机械系统MEMS三维加工制造工艺micro-electronic mechanical system （MEMS） micro-motion

Auto Identification of Rolling Layers in Roller-Compacted Concrete Dam

为鉴别在压缩压路机的水泥(RCC ) 的滚动的层自动地建水坝的一个计划被介绍。首先，一个概念的模型被开发。由使用一个计算几何学方法，第二，卷在卷压缩之间匹配的层和汽车的汽车

期刊

碾压混凝土坝自动识别滚动混凝土层概念模型几何方法工程质量RCCroller-compacted concrete dam rolling qu

Improved Pattern Tree for Incremental Frequent-Pattern Mining

由分析存在前缀树数据结构，一棵改进模式树为处理新交易被介绍。它第一在一棵词典的顺序树上存储了交易然后由在一份下降频率的订单排序每条路径重构树。当更新改进模式树时，到

期刊

增量更新挖掘模式数据结构电源端口即时通讯执行时间数据库数据集data mining association rules improved p

Effects of Concentration and Freeze-Thaw on the First Hydration Shell Structure of Zn^2＋ Ions

为了在第一水和上调查盐集中和结冰融化(英尺)的效果，在 Zn ( NO3 )Zn2+轰炸离子 2 水的溶液，扩大X光检查吸收罚款结构( EXAFS )光谱学被用来检验 Zn ( NO3 )的 Zn 小锚 EXAFS

期刊

离子水化盐浓度化锌冻融扩展X射线吸收精细结构壳结构XAFS谱EXAFSEXAFS Zn （NO3）2 aqueous solution fi

镀锌板激光焊接工艺及锌行为研究

进行了镀锌板激光焊接工艺研究，讨论了激光焊接过程中锌的气化蒸发对等离子体形成的影响。结果表明，光束模式与等离子体控制是影响焊接质量的重要因素。使用合适的焊接工艺，可获

期刊

镀锌板激光焊接锌行为等离子体zinc coated sheetlaser weldingthe effects of zinc vaporization

机载海洋激光雷达发展综述

全面地介绍了国内外机载海洋激光雷达的发展历史，对该技术的各个发展阶段进行了评述，最后对其今后的发展趋势做了展望。

期刊

机载雷达激光雷达测深水文勘测潜艇鱼群airborneoceanlidardepth sounderhydrographysubmarineunder

A Non-canonical Example to Support P Is Not Equal to NP

与本文相关的学术论文