逼近MAX 3SAT-2问题的难解性（英文）

来源 :广州大学学报：自然科学版 | 被引量 : 0次 | 上传用户：hghg2000

【摘要】

：

证明了逼近MAX 3SAT-2问题在某个常数因子内是计算难解的.首先引进了一种保留近似算法难解性的K-归约的概念;然后给出了一个从MAX 3SAT问题到MAX 3SAT-2问题K-归约.因为逼近M

【作者】

：

陈文彬

【机构】

：

广州大学计算机科学与教育软件学院

【出处】

：

广州大学学报：自然科学版

【发表日期】

：

2012年2期

【关键词】

：

NP-难解性计算复杂性近似性 NP-hardness computational complexity approximation

下载到本地 , 更方便阅读

下载此文赞助VIP

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

论文部分内容阅读

证明了逼近MAX 3SAT-2问题在某个常数因子内是计算难解的.首先引进了一种保留近似算法难解性的K-归约的概念;然后给出了一个从MAX 3SAT问题到MAX 3SAT-2问题K-归约.因为逼近MAX 3SAT问题在某个常数因子内是计算难解的,所以逼近MAX 3SAT-2问题在某个常数因子内是计算难解的.这样作为推论也可以得到逼近MAX 3SAT-3问题在某个常数因子内是计算难解的,简化了以前关于逼近MAX 3SAT-3问题难解性的证明.

其他文献

磷灰石对溶液中铀的去除行为研究

通过静态实验,分别研究了不同的时间、pH值、铀初始质量浓度、磷灰石用量等条件下磷灰石去除溶液中铀的行为.结合红外光谱、扫描电镜、X衍射和磷析出量等分析结果,初步探讨了

期刊

磷灰石溶液铀去除反应机理apatiteuranium removalreaction mechanism

一种自适应的JPEG 2000数字水印算法

为了实现信息的有效隐藏，文章提出了一种自适应的数字水印算法．算法充分利用JPEG 2000标量量化的特性进行量化编码．先利用线性反馈移位寄存器对水印图像进行加密置乱，然后进行小

期刊

JPEG2000水印小波变换移位JPEG 2000watermarkwavelet transformshift

基于波动函数的矿体矿化强度分析——以山东大尹格庄金矿为例

成矿元素品位的变化规律是矿体矿化强度变化的主要影响要素之一．应用消除趋势波动分析（DFA）方法对山东大尹格庄金矿不同穿脉Au元素品位序列的变化特征进行分析，探索序列的波动趋

期刊

消除趋势波动分析矿化强度标度不变性长程相依detrended fluctuation analysis of fluctuation. The stu

基于正交实验的空调换热器流场模拟及性能分析

文章运用Fluent软件对空调中换热器气态流场进行数值模拟分析．在进行计算网格划分以及建立控制方程基础上，对其温度场、速度场、压力场等关键性能要素进行数值模拟及过程实验．通

期刊

正交实验空调换热器流场模拟性能分析orthogonal experiment heat exchanger of air conditioning s

水胺硫磷半抗原分子的设计及其免疫效果

以水胺硫磷的特征部分为基础,设计合成半抗原O-甲基-O-2-水杨酸异丙酯硫代磷酰-6-氨基己酸（HICP）,并通过活泼酯法将其与载体蛋白BSA、OVA分别偶联制备了免疫抗原H-ICP-BSA和包

期刊

水胺硫磷半抗原多克隆抗体间接ELISAisocarbophos polyclonal antibody ic ELISA

货架期线椒内部品质的近红外漫反射光谱检测

研究了建立近红外漫反射光谱检测货架期线椒内部品质的数学模型,并对其应用价值进行了评价。采用叶绿素a、叶绿素b和类胡萝卜素含量作为评价指标,在全光谱内(400~2 500 nm)分

期刊

近红外光谱线椒叶绿素A叶绿素B类胡萝卜素near infrared spectrumLine pepperchlorophyll achl

采用非线性化学指纹图谱技术测定羊奶中掺杂牛奶的含量

为解决定量分析羊奶中掺杂牛奶的含量这一难题,提出一种非线性化学指纹图谱信息回归测定法。先测定具有不同掺杂量奶品标样的非线性化学指纹图谱,并确定其诱导时间与掺杂牛奶

期刊

非线性化学指纹图谱羊奶和牛奶含量真伪鉴别定量评价nonlinear chemical fingerprintcontents of goat and

鸡肉与虾蛄中肌原纤维蛋白磷酸化特性的比较

以鸡肉和虾蛄中的肌原纤维蛋白为原料，分别用焦磷酸钠（SPP）和三聚磷酸钠（STP）将其进行磷酸化，并制备成凝胶，测定凝胶质构特性和保水性，对比研究了二者经不同处理后肌原纤维蛋白之间的

期刊

鸡肉虾蛄肌原纤维蛋白磷酸化凝胶强度保水性chicken squilla myofibrillar protein phosphorylatio

离子排斥色谱法分析发酵液中甘油酸等代谢产物

建立了一个利用示差折光检测器检测发酵液中甘油酸等代谢产物的方法。利用磺化的苯乙烯-二乙烯共聚物作为固定相的Aminex HPX-87H离子色谱柱为分析柱，利用示差折光检测器对发

期刊

高效液相色谱甘油酸二羟基丙酮示差折光检测器high performance liquid chromatographyglyceric acid d

一类拟周期结构压电问题的双尺度分析

对一类拟周期结构压电问题的微分方程给出了双尺度渐近展开分析,运用双尺度渐近展开方法,通过构造适当的单胞函数,得到了相应问题的均匀化方程、双尺度渐近展开式及渐近误差

期刊

压电问题均匀化双尺度拟周期结构piezoelectric problem homogenization two-scale method quas

逼近MAX 3SAT-2问题的难解性（英文）

与本文相关的学术论文