Karp的21个NPC问题和部分证明

问题

1. SAT问题

问题P为若干个子句的逻辑与,每个子句是若干变量的逻辑或(P是合取范式/CNF),问是否存在一组输入,使得P为真。

根据对偶性,这一问题可以表述为:命题S是若干子句的逻辑或,每个子句是若干变量的逻辑与(S是析取范式/DNF),问S是否为恒真命题。

2. 01整数规划

给定整数矩阵C和整数向量d,问是否存在01向量x使得[latex]Cx\geq d[/latex].

注:似乎Karp原论文中此处把“大于等于”误为“等于”:

https://cs.stackexchange.com/questions/19716/0-1-integer-progr[……]

继续阅读

【翻译】“冥王星”导弹

原文:

https://www.fourmilab.ch/documents/pluto/

“冥王星”导弹

By John Walker

在二十世纪五十年代和六十年代初期,对可控核能(而不是核武器的爆炸)的应用让以前难以想象的事情成为可能,变成了简单的工程问题。“冥王星/Pluto”项目,或者叫“超音速低空导弹/SLAM”(Supersonic Low Altitude Missile),是最极端的例子之一。不像“猎户座”(Project Orion)计划,设想由核弹驱动的四千吨太空飞船;或者“Plowshare”计划,提出用核爆进行大型土木工程项目,例如挖掘新的巴拿马地峡;“冥王[……]

继续阅读

【翻译】SM-62“蛇鲨”巡航导弹

译者说明

本文系翻译,原文地址:

https://fas.org/nuke/guide/usa/icbm/sm-62.htm

译文中对单位做了转换。

SM-62“蛇鲨”(Snark)是美国在1959~1961年装备的一种洲际巡航导弹。

文末有译者额外搜集的图片。

SM-62“蛇鲨”

尽管“蛇鲨”在非官方设计中是一种洲际地对地导弹,但它的实质是一架装备涡喷发动机的小型无人机。它有两个固体燃料火箭推进器,可以从移动发射车的短发射架上发射。升空后,“蛇鲨”由一台普拉特·惠特尼J-57涡喷发动机驱动,它可以在150000英尺(译者注:约4.5万米,[……]

继续阅读

【翻译】二战中的苏军第586歼击机团

译者说明

本文为俄罗斯杂志《航空大师》(Авиамастер)于2000年3月刊登载的一篇文章,原题为《空战中的女性》(ЖЕНСКИЕ ЛИЦА——ВОЗДУШНОЙ ВОЙНЫ ),主要介绍二战中苏联第586防空歼击机团的故事。原文见:

http://soviet-aces-1936-53.ru/abc/g/gridnev.htm

翻译过程中还参考了以下网址:

http://airaces.narod.ru/woman/woman.htm

https://www.proza.ru/2017/03/26/2108

为便于阅读,人名和地名在正文中均直接写中文译名,[……]

继续阅读

三种坐标下的流体连续方程

笛卡尔坐标形式的连续方程

《流体力学》(上)(周光埛等,第二版)的第3章给出了这个方程的推导,这里列一下最终结果:

[latex]\begin{align*}
\boxed{
\frac{\partial\rho}{\partial t}+\frac{\partial(\rho u)}{\partial x}\frac{\partial(\rho v)}{\partial y}+\frac{\partial(\rho w)}{\partial z}=0
}
\end{align*}[/latex]

柱坐标形式的连续方程

在柱坐标系下:

[latex]\begin{al[……]

继续阅读

1980年代苏军新式武器艺术画(三)

系列(一):http://43.135.142.98/2017/10/21/ussr-80s-series1/

系列(二):http://43.135.142.98/2017/10/29/ussr-80s-series2/

系列(三):http://43.135.142.98/2017/10/29/ussr-80s-series3/

本文的系列(三)是史密森尼航空航天博物馆的展览。

载人航天

载人航天是美苏先进技术的象征,并有重要的军事应用。用于把航天员送上太空的技术也可以把卫星送上地球轨道。出于寻求外太空永久存在的需要,苏联从1972年开始发射“礼炮”系列空间站,并在之[……]

继续阅读

“Fear God, Honor the King”

心血来潮看了一下1998年的迪士尼动画电影《花木兰》,发现……由于导演是美国人,所以只要接受了“历史背景是近代欧洲”这个设定,在军事方面就毫无违和感!

将军推荐男主担任新组建部队指挥官。看台词,仔细感受一下。“No.1 in his class”,这是军校啊同志们。

男主的军衔:上尉,代表连级指挥官。

一个连的宿营地。正宗的西方军队单人帐篷(注意和马的比例)。至于中国古代军队,按照《李卫公兵法》:“诸围三径一,尺寸共知。复造幕,尺丈已定,每十人共一幕”,也就是说十人一个帐篷。而且中国古代军队的宿营地应该是圆形的。

细节:帐篷钉。

[……]

继续阅读

《人民日报》摘录:北京大学在1949年12月进行的课程精简改革

提高学习效率北大精简课程 文学院各系级选定重点课程 师生集中精力充实改造内容

《人民日报》1949.12.09

【本报讯】北京大学文法理工医各学院部分系级实行精简课程,以提高师生教与学的效率,并推动了课程改革。北大本期开学以来,由于学生普遍高涨的学习热情与部分学生的好高鹜远,以致选修学分数目较之往年普遍增加,结果师生整天忙于上课下课、赶看参考书、赶习题、赶报告,完全处于被动状态,无法求得透澈的了解,不能主动地有计划地展开学习。同时,又严重地影响了学生的健康,因为文理工学院学生每人每周学习时间超过七十小时,医学院则超过了八十小时。在此情况下,各系级的政治学习亦无法好好展开

针对此种情[……]

继续阅读

拯救世界的空间天气学——1967年太阳耀斑

注:这篇文章是本人“太阳活动与人类社会”课程的期末论文。

引言

假设你是美国总统。当你正在享用晚餐的时候,几名特勤局的彪形大汉冲进来,把你拖进地下会议室。国防部长告诉一脸茫然的你, 北美防空司令部的所有远程预警雷达被不明干扰源干扰,已全部瘫痪;空军的全部无线电通讯中断,正在执行空中警戒巡逻任务的B-52失去联系。这都可能是苏联发动大规模核打击的迹象。位于内布拉斯加州的战略空军司令部发来电报,询问是否让在跑道上待命的B-52升空,按预定计划执行核反击任务……

抛开艺术夸张的成分,这是真实出现过的事件:1967年5月份发生了一次大规模的太阳耀斑爆发,它严重干扰了北美的预警雷达和无线电通信[……]

继续阅读

基于MacCormack方法的Quasi-1D Isentropic Nozzle Flow数值模拟

物理模型

这篇文章是我学习《COMPUTATIONAL FLUID DYNAMICS: The Basics with Applications》(作者John D. Anderson, Jr.)的心得体会。

这里的Quasi-1D Nozzle Flow是书上第七章的内容:用MacCormack算法求解拉瓦尔喷管(convergent-divergent nozzle)中的流场。这种喷管的示意图如下:

这种喷管的横截面是漏斗状,先变窄再变宽(这就是’convergent-divergent’的由来),它可以把亚音速气流(从左端进入)加速到超音速(从右端流出),在最窄处恰[……]

继续阅读