【摘 要】
：
描述复杂性理论是一门从逻辑的角度对计算复杂性进行研究的学问。是否存在一个逻辑能在所有结构上刻画PTIME是描述复杂性理论中长期悬而未决的开问题。本文从二阶HORN逻辑的角度对描述复杂性进行研究，提出了二阶修正HORN逻辑(SO-HORNr)和修正DATALOG程序(DATALOGr)，证明了在所有结构上它们的表达能力都等价于最小固定点逻辑FO(LFP)，并且在有序结构上它们都能刻画PTIME。本文
论文部分内容阅读
描述复杂性理论是一门从逻辑的角度对计算复杂性进行研究的学问。是否存在一个逻辑能在所有结构上刻画PTIME是描述复杂性理论中长期悬而未决的开问题。本文从二阶HORN逻辑的角度对描述复杂性进行研究，提出了二阶修正HORN逻辑(SO-HORNr)和修正DATALOG程序(DATALOGr)，证明了在所有结构上它们的表达能力都等价于最小固定点逻辑FO(LFP)，并且在有序结构上它们都能刻画PTIME。本文还使用DATALOGr程序和将一个结构编码到完美二叉树中的技术证明了存在一个在PTIME中并且在子结构下保持的问题不能被FO(LFP)定义。作为推论，本文证明了SO-HORN不能刻画在PTIME中并且在子结构下保持的问题的类。从而否定地解决了Gr(a)del在20年前提出的猜想。本文还对SO-HORN逻辑进行了扩展，提出了二阶扩展HORN逻辑(SO-EHORN)和二阶扩展修正HORN逻辑(SO-EHORNr)。证明了在所有结构上，SO-EHORNr和Π1/2-EHORNr等价，它们都能刻画co-NP，而在有序结构上，SO-EHORN和Π1/2-EHORN等价，它们也都能刻画co-NP。另外，本文针对SO-KROM逻辑提出了二阶修正KROM逻辑(SO-KROMr)，二阶扩展KROM逻辑(SO-EKROM)和二阶扩展修正KROM逻辑(SO-EKROMr)。证明了在有序结构上，SO-KROMr的存在型部分Σ1/1-KROMr可以刻画NLOGSPACE，它与Σ1/1-KROM等价，而SO-EKROM与Π1/2-EKROM等价，它们都可以刻画co-NP。在所有结构上，II1/2-KROMr和Π1/2-EKROMr等价，它们也可以刻画co-NP。
其他文献
中医理论认为，气血两虚证是一种综合性疾病，常由慢性病，劳累过度，失血过多或衰老和身体衰竭引起，可导致气血功能下降或脏腑组织机能活动减退。气血两虚临床多见头晕眼花，失眠多梦，倦怠乏力。肾虚指肾脏精气阴阳不足，临床多见腰膝酸软，失眠健忘，身体乏力等。气血两虚及肾虚均可导致机体免疫功能下降，从而影响机体各功能损伤，包括骨髓造血系统、造血微环境、胸腺及脾脏细胞凋亡等。 安神补脑液主要由制何首乌，淫羊藿，
精益实践与企业运营绩效（OP）之间的关系受到学者们的广泛关注。然而，精益实践改善运营绩效的机制尚未明确。一些研究表明，精益实践活动的环境因素（例如企业规模，行业类型等）会影响企业精益实践的实施效果。然而，之前的多数研究关注的重点在外部环境因素上，并未进一步探索企业内部因素。作为企业内部重要的竞争优势的来源，运营吸收能力（OAC）可以通过整合资源来增强企业获取和利用知识的能力。因此，本研究引入运营吸
招投标制度在中国起步较晚，体制机制存在较大的完善空间，监督方法和过程控制也有待改进。在工程项目招投标过程中危害最大的现象是围标串标行为。本文通过多智能体仿真技术，使用多智能体仿真软件NetLogo构建了工程项目围标和串标行为的多智能体仿真系统，旨在通过微观现象涌现出宏观理论，从虚拟世界推断现实世界，深入分析工程项目围标串标行为的内在机制，提出治理办法。本文主要从以下三方面进行了研究： 围标串标行
近年来，工程项目工期-成本-质量多目标优化管理在工程施工领域得到广泛应用，但是随着中国社会政治经济环境的变化，传统工程项目多目标管理也随之产生部分局限性：一方面，满足环境保护要求成为工程项目施工必须考虑的因素和目标；另一方面，轨道交通建设等大型复杂工程项目受外部不确定因素影响程度较高。因此，如何在不确定因素下，平衡大型复杂工程项目的工期-成本-质量-环境多目标定量管理是当前亟待解决的问题。 本文
自20世纪80年代中国开始试行推广工程招标投标以来，中国工程项目的实施效率有了很大程度的提高，尤其是在2001年初中国颁布的《中国人民共和国招标投标法》正式实施后，中国招标投标制度在市场经济条件下进入了新的发展阶段。招标投标制度带来极大效益之余，也引发了一系列腐败问题。由于招标投标的公正性得不到有效监督，很多招投标工作在很大程度上还是流于形式，工程大多形成多参与者合谋，私下交易，暗箱操作的情形。因
立足于社会资本理论，本文进行了三个不同层面的社交网络行为研究，探讨了自我披露行为、持续使用意愿与公益项目筹款表现与社会资本的关系。希望回答(1)社会资本与人格特质如何交互影响个体在社交网络上的自我披露行为？(2)他人披露与感知社会资本如何影响社交网络持续使用意愿？(3)个体如何利用自身社会资本与披露叙述风格在社交网络中提升公益筹款完成度？这三个问题。 自我披露行为研究拓展了社会资本与自我披露研究
本体可在医学、农业、历史、军事等不同领域得到应用,其前提是要针对特定领域构建相应的领域本体或者通用本体,对该领域的知识进行建模和本体表述。现阶段有许多已经建成并应用于实践的领域本体,但是目前大部分可公开获取的资源也主要局限在几个有限的自然科学领域,而在社会科学领域,尤其在我国人文历史学科,历史领域本体资源非常稀缺,历史领域本体的构建研究还处于起步阶段。 本文基于此背景,选择七步法作为本体构建的指
21世纪以来麦氏的一些奇思妙想为公众所熟知。 但是对于麦克卢汉思想的辨析却褒贬不一。 随着互联网的兴起与繁荣，媒介技术也蓬勃发展起来，我们迎来了信息化的新纪元。麦克卢汉被学者誉为互联网大爆炸的“先知”、“圣人”和“先锋”。这使得麦克卢汉的媒介技术思想又一次呈现在众多学者的面前，因为麦克卢汉先生的思想中有太多的闪光点，值得探讨。麦克卢汉格言式的提出了“冷热媒介”、“地球村”、“内爆”、“媒介即摩擦”
百年来，我国因明的发展跌宕起伏，自1982年2月在北京召开了抢救因明座谈会之后，“抢救因明遗产、推动因明发展”便成了当前学术界的一项重要而急迫的任务。 基于我国近现代学者对吕澂因明的研究以及笔者对吕澂因明著作的研究，本文对吕澂因明研究内容进行了明确的划分，并认为吕澂的因明研究方法有其独特的形成背景，他分别受到了清代、民国、西方和日本的学风影响，形成了自己独具特色的研究方法。吕澂精通藏、梵、巴利语
魏晋时期残酷的政治斗争以及虚伪繁缛的礼教纲常给士人的身心造成严重的危害，但也促成了魏晋士人追求自由与解放的时代思想，士人的自我意识觉醒，以实现自我价值为人生目标，而最能体现自我的就是自我的身体，“身”就是“我”的代表，但代表的不是经过“三纲五常”规范后的伦理模式化的“我”，代表的是一个与众不同的“我”，通过自我身体表现出的是“我”的思想情志，所以魏晋时期士人实现自我价值的一个重要途径就是从自我的身