Forking vs Threading

So, finally after long time, i am able to figure out the difference between forking and threading :)

When i have been surfing around, i see a lots of threads/questions regarding forking and threading, lots of queries which one should be used in the applications. So i wrote this post which could clarify the difference between these two based on which you could decide what you want to use in your application/scripts.

What is Fork/Forking:

Fork is nothing but a new process that looks exactly like the old or the parent process but still it is a different process with different process ID and having  it’s own memory. Parent process creates a separate address space for child. Both parent and child process possess the same code segment, but execute independently from each other.

The simplest example of forking is when you run a command on shell in unix/linux. Each time a user issues a command, the shell forks a child process and the task is done.

When a fork system call is issued, a copy of all the pages corresponding to the parent process is created, loaded into a separate memory location by the OS for the child process, but in certain cases, this is not needed. Like in ‘exec’ system calls, there is not need to copy the parent process pages, as execv replaces the address space of the parent process itself.

Few things to note about forking are:

• The child process will be having it’s own unique process ID.
• The child process shall have it’s own copy of parent’s file descriptor.
• File locks set by parent process shall not be inherited by child process.
• Any semaphores that are open in the parent process shall also be open in the child process.
• Child process shall have it’s own copy of message queue descriptors of the parents.
• Child will have it’s own address space and memory.

Fork is universally accepted than thread because of the following reasons:

• Development is much easier on fork based implementations.
• Fork based code a more maintainable.
• Forking is much safer and more secure because each forked process runs in its own virtual address space. If one process crashes or has a buffer overrun, it does not affect any other process at all.
• Threads code is much harder to debug than fork.
• Fork are more portable than threads.
• Forking is faster than threading on single cpu as there are no locking over-heads or context switching.

Some of the applications in which forking is used are: telnetd(freebsd), vsftpd, proftpd, Apache13, Apache2, thttpd, PostgreSQL.

Pitfalls in Fork:

• In fork, every new process should have it’s own memory/address space, hence a longer startup and stopping time.
• If you fork, you have two independent processes which need to talk to each other in some way. This inter-process communication is really costly.
• When the parent exits before the forked child, you will get a ghost process. That is all much easier with a thread. You can end, suspend and resume threads from the parent easily. And if your parent exits suddenly the thread will be ended automatically.
• In-sufficient storage space could lead the fork system to fail.

What are Threads/Threading:

Threads are Light Weight Processes (LWPs). Traditionally, a thread is just a CPU (and some other minimal state) state with the process containing the remains (data, stack, I/O, signals). Threads require less overhead than “forking” or spawning a new process because the system does not initialize a new system virtual memory space and environment for the process. While most effective on a multiprocessor system where the process flow can be scheduled to run on another processor thus gaining speed through parallel or distributed processing, gains are also found on uniprocessor systems which exploit latency in I/O and other system functions which may halt process execution.

Threads in the same process share:

• Process instructions
• Most data
• open files (descriptors)
• signals and signal handlers
• current working directory
• User and group id

Each thread has a unique:

• Thread ID
• set of registers, stack pointer
• stack for local variables, return addresses
• signal mask
• priority
• Return value: errno

Few things to note about threading are:

• Thread are most effective on multi-processor or multi-core systems.
• For thread – only one process/thread table and one scheduler is needed.
• All threads within a process share the same address space.
• A thread does not maintain a list of created threads, nor does it know the thread that created it.
• Threads reduce overhead by sharing fundamental parts.
• Threads are more effective in memory management because they uses the same memory block of the parent instead of creating new.

Pitfalls in threads:

• Race conditions: The big loss with threads is that there is no natural protection from having multiple threads working on the same data at the same time without knowing that others are messing with it. This is called race condition. While the code may appear on the screen in the order you wish the code to execute, threads are scheduled by the operating system and are executed at random. It cannot be assumed that threads are executed in the order they are created. They may also execute at different speeds. When threads are executing (racing to complete) they may give unexpected results (race condition). Mutexes and joins must be utilized to achieve a predictable execution order and outcome.
• Thread safe code: The threaded routines must call functions which are “thread safe”. This means that there are no static or global variables which other threads may clobber or read assuming single threaded operation. If static or global variables are used then mutexes must be applied or the functions must be re-written to avoid the use of these variables. In C, local variables are dynamically allocated on the stack. Therefore, any function that does not use static data or other shared resources is thread-safe. Thread-unsafe functions may be used by only one thread at a time in a program and the uniqueness of the thread must be ensured. Many non-reentrant functions return a pointer to static data. This can be avoided by returning dynamically allocated data or using caller-provided storage. An example of a non-thread safe function is strtok which is also not re-entrant. The “thread safe” version is the re-entrant version strtok_r.

Advantages in threads:

• Threads share the same memory space hence sharing data between them is really faster means inter-process communication (IPC) is real fast.
• If properly designed and implemented threads give you more speed because there aint any process level context switching in a multi threaded application.
• Threads are really fast to start and terminate.

Some of the applications in which threading is used are: MySQL, Firebird, Apache2, MySQL 323

FAQs:

1. Which should i use in my application ?

Ans: That depends on a lot of factors. Forking is more heavy-weight than threading, and have a higher startup and shutdown cost. Interprocess communication (IPC) is also harder and slower than interthread communication. Actually threads really win the race when it comes to inter communication. Conversely, whereas if a thread crashes, it takes down all of the other threads in the process, and if a thread has a buffer overrun, it opens up a security hole in all of the threads.

which would share the same address space with the parent process and they only needed a reduced context switch, which would make the context switch more efficient.

2. Which one is better, threading or forking ?

Ans: That is something which totally depends on what you are looking for. Still to answer, In a contemporary Linux (2.6.x) there is not much difference in performance between a context switch of a process/forking compared to a thread (only the MMU stuff is additional for the thread). There is the issue with the shared address space, which means that a faulty pointer in a thread can corrupt memory of the parent process or another thread within the same address space.

3. What kinds of things should be threaded or multitasked?

Ans: If you are a programmer and would like to take advantage of multithreading, the natural question is what parts of the program should/ should not be threaded. Here are a few rules of thumb (if you say “yes” to these, have fun!):

• Are there groups of lengthy operations that don’t necessarily depend on other processing (like painting a window, printing a document, responding to a mouse-click, calculating a spreadsheet column, signal handling, etc.)?
• Will there be few locks on data (the amount of shared data is identifiable and “small”)?
• Are you prepared to worry about locking (mutually excluding data regions from other threads), deadlocks (a condition where two COEs have locked data that other is trying to get) and race conditions (a nasty, intractable problem where data is not locked properly and gets corrupted through threaded reads & writes)?
• Could the task be broken into various “responsibilities”? E.g. Could one thread handle the signals, another handle GUI stuff, etc.?

Conclusions:

1. Whether you have to use threading or forking, totally depends on the requirement of your application.
2. Threads more powerful than events, but power is not something which is always needed.
3. Threads are much harder to program than forking, so only for experts.
4. Use threads mostly for performance-critical applications.

References:

1. http://en.wikipedia.org/wiki/Fork_(operating_system)
2. http://tldp.org/FAQ/Threads-FAQ/Comparison.html
3. http://www.yolinux.com/TUTORIALS/LinuxTutorialPosixThreads.html
4. http://linas.org/linux/threads-faq.html

《颜勤礼碑》标点、注解及今译

唐故秘書省著作郎夔州都督府長史上護軍顏君神道碑

曾孫魯郡開國公真卿撰並書

(1)

君諱勤禮¹，字敬，琅琊臨沂²人。

高祖諱見遠³，齊御史中丞，梁武帝受禪，不食數日，一慟而絕⁴，事見《梁》、《齊》、《周書》⁵。

曾祖諱恊⁶，梁湘東王記室㕘軍，《文苑》有傳⁷。

祖諱之推，北齊⁸給事黃門侍郎⁹，隋東宮學士¹⁰，《齊書》有傳。始自南入北¹¹，今爲京兆長安人¹²。

 [註解]

1、繁簡字解：

• 諱，用於已故君王或尊長的名字前，表尊重。諱為形聲字，從言韋聲。韋依草書字形簡化為韦，則諱類推為讳。
• 禮，形聲字，從示豊聲，礼為其古字，今用作簡化字。

2、琅琊：又作琅邪，音láng yá，國內有琅琊山數處，此處則指秦置琅琊郡。秦時，在古琅琊邑置琅琊郡。東漢，琅琊郡改為琅琊國，治開陽（今臨沂老城）。琅琊臨沂（即琅琊國臨沂縣之簡稱）自此始。歷史上很多望族以琅琊為郡望，如東晉“王謝”的王家。諸葛亮也是山東琅琊人，為避戰亂隨叔父遷到荊州。據記載顏氏始祖是孔門七十二賢之首的顏回。顏子後裔世居於魯之曲阜，至二十四代嫡孫顏盛，遷琅琊臨沂孝悌里。顏氏後人皆自稱“琅琊臨沂人”。

3、繁簡字解：

• 見，會意字，從目從儿（人），今依草書字形簡化為见。
• 遠，形聲字，从辵(chuò，俗稱走之，即辶)，袁声。簡化字把聲旁袁置換為元，即远，成為新形聲字。

4、東晉滅亡後，南朝宋（420-589）、齊（479-502）、梁（502-557）、陳（557-589）如穿梭般交替更迭。在齊朝，御史中丞是負責糾察彈劾官僚的最高官員。齊朝倡節儉，政治清明，後因內亂被梁武帝蕭衍所代，顏見遠絕食而殉國，可見顏氏的忠烈源遠流長。梁武帝就是編《昭明文選》的昭明太子蕭統的老爹，倒行逆施士族門閥制，對百姓則實施殘暴苛政，竟也在位48年。《梁書》列傳第四十四《顏協傳》載：“高祖受禪，見遠乃不食，發憤數日而卒。高祖聞之曰：‘我自應天從人，何預天下士大夫事？而顏見遠乃至於此也。’”

繁簡字解：

• 齊，依草書筆意簡化為齐。
• 慟，本義為大哭，《說文》：“大哭也。”今類推簡化為恸。

5、《梁書》、《齊書》和《周書》名列“二十四史”，為貞觀十年（636）魏徵主持編寫，歷時七年修成。《梁書》、《陳書》、《齊書》、《周書》、《隋書》稱五代史，時稱良史。

6、繁簡字解：

• 恊，“協”之俗寫，音xié，宋孫奕《履齋示兒編》引《字譜總論訛字》云：“博、協皆從十，俗皆從忄。”《顏氏家廟碑》作“協”，今簡化為协，以二點代指二力字。

7、梁湘東王為梁武帝蕭衍第三子，名蕭繹。記事參軍是掌管軍中文書的官員。顏見遠為梁朝篡齊而死節，兒子顏協也得接著當梁朝的官。《梁書》列傳第四十四《文學》有《顏協傳》，《南史》列傳第六十二《文學》亦有《顏協傳》。但唐姚思廉撰《梁書》、唐李延壽撰《南史》均無《文苑傳》，倒是李延壽撰《北史》之《文苑》有《顏之推傳》。所以，此處“文苑”應為“文學”，係魯公筆誤。清董誥編《全唐文》上作“文學”，是對的。

繁簡字解：

• 東，會意字，太陽昇起，懸於樹中，其方向即為東，今依草書字形簡化為东。
• 記，形聲字，從言己聲，類推簡化為记。
• 㕘：《康熙字典》引《廣韻》：參俗作叅。而顏真卿手寫為㕘（心字底寫作小）。正字為參，會意字，人字頭上有三星，下加義符彡（shān），表示星光閃耀，字義為星名，二十八宿之一。今依草書筆意簡化為参。
• 軍：會意字，從車從勹（bāo,包裹），古代車戰中以車圍作營壘。今類推簡化為军。
• 傳:形聲兼會意字，從人專聲，專兼表轉動義，字義為驛站。《顏勤禮碑》中，專無論作為單字還是偏旁，均省寫作専。傳今類推簡化為传。

8、北朝先後有北魏（386-534）、東魏（534-550）、北齊（550-577）、西魏（535-556）和北周（557-581）等朝代。南朝禁碑，書法以尺牘行草為時尚。北朝刻石書法棱角鋒利，質樸勁健，後世統稱為魏碑。魏碑之北魏（386-534）晚於三國曹魏（220-265）一百二十餘年，勿混為一談。

9、給事黃門侍郎：黃門即皇宮門，給事黃門侍郎是侍從皇帝，傳達詔命的官員。史稱顏之推為“顏黃門”，在下文中魯公直接以“黃門”代顏之推的名諱。《顏氏家訓》就是顏之推的傳世之作，後世又稱作《黃門家訓》。

繁簡字解：

• 門，象形字。今依行書字形簡化為门，二處門樞簡略為一點一折。

10、太子所居之宮稱為東宮。東宮學士為太子東宮裡掌管典禮、編撰的文官。

繁簡字解：

• 學，本字為壆，後省土，加義符子，為學。簡化字取其草書字形，作学。簡化字学字頭切勿與尚字頭（如賞裳黨當）混淆。以學為聲符的字如黌、覺等。

11、顏之推自南朝入北朝做官，隋統一後再出仕，故曰“始自南入北”。

12、京兆，指京師所在地區，而京畿則指京師及周圍的地區。

繁簡字解：

• 爲，異體字作為，今依草書字形簡化作为。
• 長，象形字，今依草書字形簡化為长。

[今譯]

君名諱勤禮，字為敬，琅琊臨沂人。

勤禮君的高祖名諱為見遠，是齊朝的御史中丞。梁武帝受禪登基，他絕食數天，一聲痛哭，與世長辭，此事記載于《梁書》、《齊書》和《周書》中。

勤禮君的曾祖名諱為協，曾任梁湘東王的記事參軍，《梁書•文學》中有傳記。

勤禮君的祖父名諱為之推，曾任北齊的給事黃門侍郎，後任隋朝的東宮學士，《齊書》有他的傳記。從之推公開始從南朝入北朝為官，所以顏氏如今是京兆長安人。

(2)

父諱思魯，博學善¹属文²，尤工詁訓³，仕隋司經局校書⁴、東宮學士、長寧王侍讀⁵，與沛國劉臻辯論經義⁶，臻屢屈焉⁷。《齊書·黃門傳》云，集序君自作⁸。後加踰岷將軍⁹。

[註解]

http://blog.sina.com.cn/s/blog_4b013c240100txli.html

1、善，本字為“譱”，會意字，羊意為美味，雙言“誩”(音jìng)義為競言爭辯，會連連稱美之意。後從簡為一“言”，異寫作“善”。《顏勤禮碑》中共有善字六處，均寫作異體“𠵊”（上羊下古）。

2、属，此處音zhǔ，“屬”之俗寫。屬，形聲字，從尾蜀聲，本義為連接，引申為連綴，撰寫。屬文，撰寫文章。《顏勤禮碑》中“屬”字無論音zhǔ或shǔ，均從俗寫作“属”，即所謂“手頭字”。手頭字是1956年簡化字的一個重要來源。

3、詁訓，又作訓詁，訓指用通俗語言解釋字義，詁指用當代語言解釋古代語言文字，譬如本文對字義字形的註解即屬訓詁。訓詁學是我國傳統的語文學——小學的重要範疇。

4、司經局：官署名，南朝梁太子官署有典經局，隋稱司經局，唐一度改名桂坊，有洗馬等官，掌太子宮中圖書。明清時仍有此官署，清亡乃廢。校書，掌管校勘、管理典籍的官職。

繁簡字解：

• 隋：楊堅襲父爵為隨國公，開國後立國號為隨，因隨字有走義，故去“辶”為隋。儘管如此，隋僅享國祚短短三十八年。
• 經：本字為巠，後加形旁為經，異體作𦀇、経，簡化字為“经”。經字本義為織布時的縱向紗線，與“緯”相對，引申指經久不變的法則，再引申為堪為思想、道德、行為規範的著作。

5、長寧王，楊儼，隋太子楊勇之子，隋文帝楊堅之長孫，六歲封長寧郡王。楊勇廢，長寧王亦遭黜，後為煬帝所鴆。侍讀，陪侍帝王讀書論學或為皇子等授書講學的文官。

繁簡字解：

• 寧：本字為“寍”，从宀（mián，房子），从心，从皿，會有住有吃心乃安之意。加“丂”為“寧”。另有甯字，用於“甯願”，同“寧願”，另為姓。今皆從民間白字簡化為“宁”。但正字中本有“宁”念作zhù，是“貯”之本字，因雀占鳩巢，貯、佇字形被迫變為贮、伫。
• 讀：賣以草書筆意簡化為“卖”，則讀類推簡化為“读”。

6、沛國劉臻：《文苑》載“劉臻，字宣摯，沛國相人也。”隋文帝統一中國後，未設置藩王，故並無沛國，這裡是以古國名為籍貫。《文苑》又載：“皇太子勇引為學士，甚親狎之。臻無吏幹，又性惚怳，耽經覃思。至於世事，多所遺忘。”又載“精於兩漢書，時人稱為漢聖。”可見劉臻是個皓首窮經的老夫子，太子楊勇與之親昵。

繁簡字解：

• 與：從与，從舁（yú）。《說文》視“與”和“与”為兩個不同的字，今人考證“与”為其古字。顏魯公在數通碑帖有均有混用二字處，《顏勤禮碑》中有一處寫作“与”（見下文）。今簡化字採用古字“与”。
• 國：從“囗”（wéi，表邊界圍繞），從或。“或”與“域”是一個字，為“國”之本字。異體或作“囻”，太平天國造“囯”字，今簡化為“国”。
• 劉：會意字，從卯（表剖分），從金，從刀，本義為砍殺。另為姓。1935年民國《簡體字表》收錄“刘”，淵源不詳。
• 辯：形聲字，從言，辡(biǎn)聲，本義爭論。另，辨，從刀辡聲，本義為區分，辨別。
• 論：形聲字，從言，侖聲。以草書字形簡化為“论”。
• 義：會意字，《說文》：“己之威儀也，从我羊。”1935年民國《簡體字表》收錄“义”，或為民間俗寫。

7、繁簡字解：

• 屢：形聲字，從尸（房屋之象形，非指身體），婁聲。屢本義為樓房，由樓房層層相連，引申為連續，而樓房之義另造形聲字“樓”來表達。婁依草書字形簡化為“娄”，則屢類推簡化為“屡”。

8、史稱顏之推為“顏黃門”，故魯公避之推諱稱《顏之推傳》為《黃門傳》。《北齊書》列傳第三十七《顏之推傳》載：“之推在齊有二子，長曰思魯，次曰敏楚，不忘本也。《之推集》在，思魯自為序錄。”

9、踰岷將軍：據《隋書》卷二十七志第二十二《百官中》：“特進、左右光祿、金紫、銀青等光祿大夫，用人俱以舊德就閑者居之。自一品已下，從九品已上，又有驃騎、車騎……橫海、逾岷、越嶂……等將軍，以褒賞勳庸。”可見踰岷將軍是無具體職責不理事的散官，官階為從六品。踰，同“逾”。逾岷越嶂，語出禰衡《鸚鵡賦》。

繁簡字解：

• 將：會意兼形聲字，谷衍奎《漢字源流詞典》：“從肉，爿（qiáng）聲……另加義符又（寸）……本義當爲奉獻祭享。”顏魯公把該字右側寫作“寽”。簡化字為“将”，把聲符爿簡化，把斜月（即肉）中的二點去掉一點，想必是當代的將軍肚太多，急需減肥。

[今譯]

勤禮君的父親名諱為思魯，他學識廣博，擅寫文章，特別精通訓詁學。在隋朝時他擔任司經局的校書、東宮學士、長寧王的侍讀等官職。他曾與劉臻辯論經籍義理，劉臻屢屢理屈辭窮。《齊書•顏之推傳》記載，《顏之推集》的序都是思魯親自撰寫。後來他被加封為踰岷將軍。

(3)

太宗爲秦王¹，精選僚属，拜記室參軍²，加儀同³。娶御正中大夫殷英童女，《英童集》⁴呼顏郎是也，更唱和者二十餘首。《溫大雅傳》云⁵，初君在隋，與大雅俱仕東宮，弟愍楚與彥博同直內史省⁶，愍楚弟遊秦與彥將俱典祕閣⁷。二家兄弟，各為一時人物之選⁸。少時學業，顏氏為優，其後軄位⁹，溫氏為盛。事具唐史¹⁰。

[註解]

1、公元618年李淵在長安稱帝，國號唐，李世民被封為秦王。

2、記室參軍：掌管軍隊文書起草、記錄的書記官員。

3、儀同：即“儀同三司”。漢稱太尉、司徒、司空為三司。儀同三司即雖然不是三司但儀制同于三司，隋唐時為散官，與如今的“相當於廳級”、“相當於副總理級”大致一個意思。

4、《英童集》，殷英童的個人詩文集，早佚。該書中稱呼顏思魯為“顏郎”。不如此斷句，則“集”字與“呼”字連讀，就沒法解了。網絡電子版《全唐文》斷句有誤。

5、溫大雅（約572-629年），字彥弘，仕唐官至禮部尚書，封黎國公。《溫大雅傳》原文如下：“初，大雅在隋，與顏思魯俱在東宮，彥博與思魯弟湣楚同直內史省，彥將與湣楚弟遊秦典校祕閣。二家兄弟，各為一時人物之選。少時學業，顏氏為優﹔其後職位，溫氏為盛。”可見顏真卿基本是引用其原文。其弟大臨（彥博）、大有（彥將），溫彥博是唐貞觀年間著名宰相，《虞恭公溫彥博碑》為歐陽詢所書名碑。

繁簡字解：

•  云：象形字，像雲彩迴旋狀，本義為“山川氣也”。該字衍生出“說”義後，本義採用新造形聲字“雲”，而“云”字專用於“言說”義，明確分工。簡化字將二義重新歸併為“云”字。無論是繁簡字，“人雲亦雲”均是錯誤的。

6、直：同“值”，當值，值班。內史省：隋確立中央官僚體系為“三省六部制”，三省為內史省（即中書省）、門下省、尚書省。其中內史省是掌管制令決策的權力中心。

7、典：主持，主管。祕閣，是宮廷藏書機構，自晉、南朝宋至隋、唐，皇宮皆設有秘閣藏書，宋《淳化閣帖》全稱實為《淳化秘閣帖》。

繁簡字解：

• 祕：形聲字，從示必聲，義符示為祭祀神靈義。現本字“祕”被棄，其俗寫“秘”反行世。《康熙字典》：“《正字通》从示从必。俗从禾作秘，譌。”
• 閣：形聲字，從門各聲，今類推簡化為“阁”。

8：繁簡字解：

• 時：形聲字，從日寺聲。今依草書字形簡化為“时”。
• 選：形聲字，從辵巽聲。1935年民國《簡體字表》有“选”，為新造形聲字，今用作簡化字。

9、繁簡字解：

• 業：會意字，从丵（zhuó）从巾。今取其上部 “业”為簡化字。實則古字“㐀”為古“丘”字。顏真卿《元次山碑》有“前是泌南戰士積骨者，君悉收瘞，刻石立表，命之曰哀丘”句，其中“哀丘”即寫作“哀业”。參見：http://blog.sina.com.cn/s/blog_4b013c240100fswv.html
• 優：形聲字，從人憂聲。簡化字“优”為新造形聲字。
• 職：形聲字，從耳戠(zhí)聲，本義為聽而記之，故以耳為形旁。異體字寫作“軄”，改用“身”為義符。《康熙字典》：“軄，《玉篇》俗職字。”簡化字“职”為新造形聲字。

10、如今提《唐史》，一般指《舊唐書》和《新唐書》。五代後晉（936-947）時官修的《舊唐書》，原名《唐書》，宋代歐陽修、宋祁等編寫《新唐書》問世後，改稱《舊唐書》。中唐的顏真卿自然無緣讀到後朝史家所修的《舊唐書》和《新唐書》，則此處的“唐史”二字所指為何？原來唐代歷任皇帝均設史官修《實錄》（春秋時便有“董狐之筆”！），並先後有吳兢、韋述、柳芳等根據《實錄》三篡《國史》，後世史家修《唐書》皆以此為底本。《溫大雅傳》當首見諸唐史官《國史》，後世舊新《唐書》因之。顏真卿“事具唐史”即是指唐史官所輯錄的《實錄》和《國史》。清人編《全唐文》時，將這四字改為“事具國史”。

[今譯]

太宗皇帝被封秦王後，精選手下的幕僚，他被授予記室參軍的職務，並加授儀同一職。他娶御正中大夫殷英童的女兒為妻，《英童集》所說的顏郎就是指他，而且該書還收錄了他們之間來往唱和的詩作二十餘首。《溫大雅傳》記載，最初他在隋朝，與大雅先生同在東宮做官，思魯公的弟弟湣楚與大雅先生的弟弟彥博同在內史省當值，湣楚的弟弟游秦與彥博的弟弟彥將一同掌管秘閣。顏溫兩家的兄弟，都是當時的著名人物。年輕時的學業，以顏氏兄弟為優，後來官場的職位，則以溫家兄弟更為顯赫。這些事在《唐史》中有詳細記載。

(4)

君幼而朗晤¹，識量弘遠²，工於篆籀³，尤精詁訓⁴，祕閣司經史籍多所刊定⁵。義寜元秊⁶十一月，從太宗平京城，授朝散正議大夫勳⁷，解褐秘書省校書郎⁸。武德中授右領左右府鎧曹參軍⁹，九秊十一月授輕車都尉兼直秘書省。貞觀三秊六月兼行雍州參軍事，六秊七月授著作佐郎，七秊六月授詹事主簿，轉太子内直監，加崇賢館學士¹⁰。宮廢，出，補蔣王文學¹¹，弘文館學士¹²。永徽元秊三月制曰，具官君“學藝優敏，宜加獎擢”¹³。乃拜陳王属學士如故，遷曹王友¹⁴。無何¹⁵，拜秘書省著作郎。

[註解]

1、“晤”字的今義以“會晤”為主，不過該字的本義卻是“聰明”。這是個形聲字，《说文》：“明也。从日吾聲。”《顏氏家廟碑》中作“朗悟”，可見“晤”與“悟”字義相近。

2、繁簡字解：

• 識：形聲字，從言，戠(zhí)聲。簡化字“识”以“只”作聲旁，為新造形聲字。
• 弘：形聲字，從弓厶(gōng)，弓響之大聲，義廣大。今多寫作“宏”。

3、篆籀：篆，專指秦朝統一文字後的小篆；籀，音zhòu，即秦之前的大篆。有“史籀所作為大篆，李斯所作為小篆”的說法。史籀，相傳是周宣王時太史，作《史籀篇》。

4、詁訓，即訓詁學，探究古文字義的學問，是傳統“小學”之一。

5、祕閣，見前註。司經，即司經局，掌管太子東宮圖書的機構。全句義：秘閣和司經局的史籍，大多都是經過他修正、定稿的。

6、義寧元年：西元617年，李世民揮師攻破長安，立代王楊侑為帝即隋恭帝，改元義寧元年。次年，李淵受禪稱帝，隋亡。

7、查唐朝官制，朝散大夫等級為從五品下，正議大夫為正四品上，可見顏勤禮先封朝散大夫，後升任正議大夫。勳官實際上是沒有實職的榮譽稱號。

繁簡字解：

• 從：古字為象形字“从”，後加義符辵(chuò)，篆文為 ，楷化作從。簡化字則恢復古字，作“从”。
• 議：形聲字，從言義聲。簡化字類推為“议”。
• 勳：形聲字，金文作“勛”，從力員聲。篆文為“勳”，改聲旁為熏。楷化後有勛、勳而字形。今依古文字形類推簡化為“勋”。

8、解褐：褐即平民所穿的粗布衣。解褐，意即脫去布衣，擔任官職。因為上句的勳是沒有實職的，此處才曰“解褐”。秘書省是專門管理國家圖書典籍的官署，在隋唐中央官制中並不屬中樞三省（中書、門下、尚書）之列，其長官為秘書省監，從三品。校書郎為正九品上，掌校對典籍，刊正文章。

9、武德為唐高祖李淵年號，西元618~627年。隋文帝置左右領左右府，唐仍之，執掌護衛侍從等。鎧曹參軍是主管皇帝和太子行路儀仗的官員。

10、一串官制名，拗口且費解，大致如下：

• 輕車都尉，從四品勳官，非實職。“兼直秘書省”的“直”，即“值”的本字，當值之義。
• 參軍事，又稱參軍，即參謀軍務之義，大概相當於今天的參謀。
• 著作佐郎：品級為從六品上，比校書郎高升了好幾級！
• 詹事主簿：詹事府是太子東宮的最高行政機構，詹事主簿是負責來往政務文書的收發、審核、用印的職務，品級為從七品上。
• 太子內直監：正六品，此時的太子是太宗長子李承乾，該職務的權責暫未詳。
• 崇賢館學士：貞觀十三年（639年）設置崇賢館，歸東宮直轄。上元二年（675年）因避太子李賢名，改為崇文館。置學士掌經籍圖書，教授生徒。學生均為皇族貴戚及高級京官子弟。
• 東宮太子是皇帝的接班人，置太師，太傅，太保及少師，少傅，少保，專司訓導。此外，在其府下還有一套文武人馬，其制擬中央官制，門下坊擬門下省，統領司經、宮門、內直、典膳、藥藏、齋帥等六局。典書坊擬內史省，下文的“太子通事舍人”即任職典書坊。家令寺、率更令寺、僕寺，制擬中央諸寺諸監。歐陽詢便曾任太子率更令，故世稱歐陽率更。

繁簡字解：

• 館：形聲字，從食官聲，本義為招待食宿的客舍。異體字“舘”以“舍”為形旁，強調其屋舍的屬性。今簡化字依偏旁類推為“馆”。

11、“宮廢”，指東宮太子李承乾被廢一事。蔣王，唐太宗子李惲封蔣王。文學，官名，漢代於州郡及國王設置文學，或稱文學掾、文學史，為後世教官所由來。隋唐時，太子及諸王下亦置文學。

繁簡字解：

• 廢：形聲字，从广(yǎn)發聲，本義為房屋傾倒。今類推簡化為“废”。
• 補：形聲字，從从衣甫聲。今簡化字“补”以“卜”為聲旁，為新造形聲字。

12、唐武德四年（西元621年），時為天策上將軍的李世民設立文學館，作為其智囊機構，聚集了房玄齡、杜如晦、虞世南等政治人才，時稱“十八學士”，顏勤禮胞兄顏相時名列其中。文學館的建立，標誌著李唐從武功到文治的轉折。魏晉時盛行門閥制度，官僚階層被幾個望族壟斷（如王謝）。隋廢“九品中正制”開科考先河，唐承襲科考取仕制度，極大地激發了儒家讀書人“修齊治平”的政治熱情，故唐太宗才有那句著名的豪語“天下英雄盡入吾彀中矣”。李世民登基後，下令在弘文殿聚書20萬卷，改修文館為弘文館，又集聚一批英才，“聽朝之際，引入殿內，講論文義……或至夜分而罷。”兩館相繼只有幾年，薈萃人才，開拓文化，功不可沒。

13、永徽，唐高宗年號，永徽元年為西元650年。制，帝王“命為制，令為詔”，帝王的命令統稱為制或詔。具官，官爵品級的省寫。唐宋後，官吏在公文函牘或其他應酬文字上，常把應寫明的官爵品級簡寫為“具官”，又稱“具位”。

繁簡字解：

• 藝：本字為埶，後加艸為蓺，再加云為藝。本義為種植。簡化字“艺”為新造形聲字。
• 獎：形聲字，從犬，將聲，本義為發聲驅使犬隻。後形旁犬訛變為大，簡化字再省寸，字形為“奖”。

14、陳王、曹王，李世民的皇子皇孫封王。王友，是輔佐、侍從之類的官職，與上文“文學”類似，合稱“友學”。可見王爺連朋友都不能自己隨意交，那也得封。

繁簡字解：

• 遷：形聲字，從辵䙴聲，本義為移動，引申為官場升職。簡化字為“迁”，以千為簡化聲符，為新造形聲字。

15、無何：不久。

繁簡字解：

• 無：《说文解字》以“无”為其古字。無為象形字，象人持器具舞蹈狀，即舞之本字。篆文以“舞”表舞蹈，以“無”表沒有之義。今簡化字“无”取其古字。

[今譯]

勤禮君小時候就明朗聰穎。他見識氣度寬宏深遠，擅長篆書，尤其精通訓詁學，秘閣和司經局的史書，很多都經過他修正、定稿。義寧元年十一月，他跟隨太宗平定京城，被授予朝散大夫和正議大夫的勳官，擔任秘書省校書郎的官職。武德年間授予右領左右府鎧曹參軍一職，武德九年十一月授予輕車都尉，並兼職于秘書省。貞觀三年六月兼任雍州的參軍職務，六年七月授予著作左郎，其年六月授予詹事主簿，轉任太子內直監，加任崇賢館學士。東宮太子被廢後，勤禮君出宮，補任蔣王文學一職，後任弘文館學士。永徽元年三月皇帝下詔令說，官員勤禮君“學藝優敏，宜加獎擢”，於是官拜陳王部屬學士，一如從前。後又調任曹王友。不久，又授予秘書省著作郎之職。

The 17 Equations That Changed The Course Of History

Mathematics is all around us, and it has shaped our understanding of the world in countless ways.

In 2013, mathematician and science author Ian Stewart published a book on 17 Equations That Changed The World. We recently came across this convenient table on Dr. Paul Coxon's twitter account by mathematics tutor and blogger Larry Phillips that summarizes the equations. (Our explanation of each is below):

Larry Phillips, via @paulcoxon on Twitter

Here is a little bit more about these wonderful equations that have shaped mathematics and human history:

Shutterstock/ igor.stevanovic

1) The Pythagorean Theorem: This theorem is foundational to our understanding of geometry. It describes the relationship between the sides of a right triangle on a flat plane: square the lengths of the short sides, a and b, add those together, and you get the square of the length of the long side, c.

This relationship, in some ways, actually distinguishes our normal, flat, Euclidean geometry from curved, non-Euclidean geometry. For example, a right triangle drawn on the surface of a sphere need not follow the Pythagorean theorem.

2) Logarithms: Logarithms are the inverses, or opposites, of exponential functions. A logarithm for a particular base tells you what power you need to raise that base to to get a number. For example, the base 10 logarithm of 1 is log(1) = 0, since 1 = 100; log(10) = 1, since 10 = 101; and log(100) = 2, since 100 = 102.

The equation in the graphic, log(ab) = log(a) + log(b), shows one of the most useful applications of logarithms: they turn multiplication into addition.

Until the development of the digital computer, this was the most common way to quickly multiply together large numbers, greatly speeding up calculations in physics, astronomy, and engineering. 

3) Calculus: The formula given here is the definition of the derivative in calculus. The derivative measures the rate at which a quantity is changing. For example, we can think of velocity, or speed, as being the derivative of position — if you are walking at 3 miles per hour, then every hour, you have changed your position by 3 miles.

Naturally, much of science is interested in understanding how things change, and the derivative and the integral — the other foundation of calculus — sit at the heart of how mathematicians and scientists understand change.

Wikimedia Commons

Isaac Newton

4) Law of Gravity: Newton's law of gravitation describes the force of gravity between two objects, F, in terms of a universal constant, G, the masses of the two objects, m1 and m2, and the distance between the objects, r. Newton's law is a remarkable piece of scientific history — it explains, almost perfectly, why the planets move in the way they do. Also remarkable is its universal nature — this is not just how gravity works on Earth, or in our solar system, but anywhere in the universe.

Newton's gravity held up very well for two hundred years, and it was not until Einstein's theory of general relativity that it would be replaced.

5) The square root of -1: Mathematicians have always been expanding the idea of what numbers actually are, going from natural numbers, to negative numbers, to fractions, to the real numbers. The square root of -1, usually written i, completes this process, giving rise to the complex numbers.

Mathematically, the complex numbers are supremely elegant. Algebra works perfectly the way we want it to — any equation has a complex number solution, a situation that is not true for the real numbers : x2 + 4 = 0 has no real number solution, but it does have a complex solution: the square root of -4, or 2i. Calculus can be extended to the complex numbers, and by doing so, we find some amazing symmetries and properties of these numbers. Those properties make the complex numbers essential in electronics and signal processing.

Wikimedia Commons

A cube.

6) Euler's Polyhedra Formula: Polyhedra are the three-dimensional versions of polygons, like the cube to the right. The corners of a polyhedron are called its vertices, the lines connecting the vertices are its edges, and the polygons covering it are its faces.

A cube has 8 vertices, 12 edges, and 6 faces. If I add the vertices and faces together, and subtract the edges, I get 8 + 6 - 12 = 2.

Euler's formula states that, as long as your polyhedron is somewhat well behaved, if you add the vertices and faces together, and subtract the edges, you will always get 2. This will be true whether your polyhedron has 4, 8, 12, 20, or any number of faces.

Euler's observation was one of the first examples of what is now called a topological invariant — some number or property shared by a class of shapes that are similar to each other. The entire class of "well-behaved" polyhedra will have V + F - E = 2. This observation, along with with Euler's solution to the Bridges of Konigsburg problem, paved the way to the development of topology, a branch of math essential to modern physics.

economicshelp.org

The normal distribution.

7) Normal distribution: The normal probability distribution, which has the familiar bell curve graph to the left, is ubiquitous in statistics.

The normal curve is used in physics, biology, and the social sciences to model various properties. One of the reasons the normal curve shows up so often is that it describes the behavior of large groups of independent processes.

8) Wave Equation: This is a differential equation, or an equation that describes how a property is changing through time in terms of that property's derivative, as above. The wave equation describes the behavior of waves — a vibrating guitar string, ripples in a pond after a stone is thrown, or light coming out of an incandescent bulb. The wave equation was an early differential equation, and the techniques developed to solve the equation opened the door to understanding other differential equations as well.

9) Fourier Transform: The Fourier transform is essential to understanding more complex wave structures, like human speech. Given a complicated, messy wave function like a recording of a person talking, the Fourier transform allows us to break the messy function into a combination of a number of simple waves, greatly simplifying analysis.

 The Fourier transform is at the heart of modern signal processing and analysis, and data compression. 

10) Navier-Stokes Equations: Like the wave equation, this is a differential equation. The Navier-Stokes equations describes the behavior of flowing fluids — water moving through a pipe, air flow over an airplane wing, or smoke rising from a cigarette. While we have approximate solutions of the Navier-Stokes equations that allow computers to simulate fluid motion fairly well, it is still an open question (with a million dollar prize) whether it is possible to construct mathematically exact solutions to the equations.

11) Maxwell's Equations: This set of four differential equations describes the behavior of and relationship between electricity (E) and magnetism (H).

Maxwell's equations are to classical electromagnetism as Newton's laws of motion and law of universal gravitation are to classical mechanics — they are the foundation of our explanation of how electromagnetism works on a day to day scale. As we will see, however, modern physics relies on a quantum mechanical explanation of electromagnetism, and it is now clear that these elegant equations are just an approximation that works well on human scales.

12) Second Law of Thermodynamics: This states that, in a closed system, entropy (S) is always steady or increasing. Thermodynamic entropy is, roughly speaking, a measure of how disordered a system is. A system that starts out in an ordered, uneven state — say, a hot region next to a cold region — will always tend to even out, with heat flowing from the hot area to the cold area until evenly distributed.

The second law of thermodynamics is one of the few cases in physics where time matters in this way. Most physical processes are reversible — we can run the equations backwards without messing things up. The second law, however, only runs in this direction. If we put an ice cube in a cup of hot coffee, we always see the ice cube melt, and never see the coffee freeze.

Associated Press

Albert Einstein

13) Relativity: Einstein radically altered the course of physics with his theories of special and general relativity. The classic equation E = mc2 states that matter and energy are equivalent to each other. Special relativity brought in ideas like the speed of light being a universal speed limit and the passage of time being different for people moving at different speeds.

General relativity describes gravity as a curving and folding of space and time themselves, and was the first major change to our understanding of gravity since Newton's law. General relativity is essential to our understanding of the origins, structure, and ultimate fate of the universe.

14) Schrodinger's Equation: This is the main equation in quantum mechanics. As general relativity explains our universe at its largest scales, this equation governs the behavior of atoms and subatomic particles.

Modern quantum mechanics and general relativity are the two most successful scientific theories in history — all of the experimental observations we have made to date are entirely consistent with their predictions. Quantum mechanics is also necessary for most modern technology — nuclear power, semiconductor-based computers, and lasers are all built around quantum phenomena.

15) Information Theory: The equation given here is for Shannon information entropy. As with the thermodynamic entropy given above, this is a measure of disorder. In this case, it measures the information content of a message — a book, a JPEG picture sent on the internet, or anything that can be represented symbolically. The Shannon entropy of a message represents a lower bound on how much that message can be compressed without losing some of its content.

Shannon's entropy measure launched the mathematical study of information, and his results are central to how we communicate over networks today.

16) Chaos Theory: This equation is May's logistic map. It describes a process evolving through time — xt+1, the level of some quantity x in the next time period — is given by the formula on the right, and it depends on xt, the level of x right now. k is a chosen constant. For certain values of k, the map shows chaotic behavior: if we start at some particular initial value of x, the process will evolve one way, but if we start at another initial value, even one very very close to the first value, the process will evolve a completely different way.

We see chaotic behavior — behavior sensitive to initial conditions — like this in many areas. Weather is a classic example — a small change in atmospheric conditions on one day can lead to completely different weather systems a few days later, most commonly captured in the idea of a butterfly flapping its wings on one continent causing a hurricane on another continent. 

17) Black-Scholes Equation: Another differential equation, Black-Scholes describes how finance experts and traders find prices for derivatives. Derivatives — financial products based on some underlying asset, like a stock — are a major part of the modern financial system.

The Black-Scholes equation allows financial professionals to calculate the value of these financial products, based on the properties of the derivative and the underlying asset.

Read more: http://www.businessinsider.com/17-equations-that-changed-the-world-2014-3#ixzz2wVdPUf4h

什么是P问题、NP问题和NPC问题

http://www.matrix67.com/blog/archives/105

    这或许是众多OIer最大的误区之一。
    你会经常看到网上出现“这怎么做，这不是NP问题吗”、“这个只有搜了，这已经被证明是NP问题了”之类的话。你要知道，大多数人此时所说的NP问题其实都是指的NPC问题。他们没有搞清楚NP问题和NPC问题的概念。NP问题并不是那种“只有搜才行”的问题，NPC问题才是。好，行了，基本上这个误解已经被澄清了。下面的内容都是在讲什么是P问题，什么是NP问题，什么是NPC问题，你如果不是很感兴趣就可以不看了。接下来你可以看到，把NP问题当成是 NPC问题是一个多大的错误。

    还是先用几句话简单说明一下时间复杂度。时间复杂度并不是表示一个程序解决问题需要花多少时间，而是当问题规模扩大后，程序需要的时间长度增长得有多快。也就是说，对于高速处理数据的计算机来说，处理某一个特定数据的效率不能衡量一个程序的好坏，而应该看当这个数据的规模变大到数百倍后，程序运行时间是否还是一样，或者也跟着慢了数百倍，或者变慢了数万倍。不管数据有多大，程序处理花的时间始终是那么多的，我们就说这个程序很好，具有O(1)的时间复杂度，也称常数级复杂度；数据规模变得有多大，花的时间也跟着变得有多长，这个程序的时间复杂度就是O(n)，比如找n个数中的最大值；而像冒泡排序、插入排序等，数据扩大2倍，时间变慢4倍的，属于O(n^2)的复杂度。还有一些穷举类的算法，所需时间长度成几何阶数上涨，这就是O(a^n)的指数级复杂度，甚至O(n!)的阶乘级复杂度。不会存在O(2*n^2)的复杂度，因为前面的那个“2”是系数，根本不会影响到整个程序的时间增长。同样地，O (n^3+n^2)的复杂度也就是O(n^3)的复杂度。因此，我们会说，一个O(0.01*n^3)的程序的效率比O(100*n^2)的效率低，尽管在n很小的时候，前者优于后者，但后者时间随数据规模增长得慢，最终O(n^3)的复杂度将远远超过O(n^2)。我们也说，O(n^100)的复杂度小于O(1.01^n)的复杂度。
    容易看出，前面的几类复杂度被分为两种级别，其中后者的复杂度无论如何都远远大于前者：一种是O(1),O(log(n)),O(n^a)等，我们把它叫做多项式级的复杂度，因为它的规模n出现在底数的位置；另一种是O(a^n)和O(n!)型复杂度，它是非多项式级的，其复杂度计算机往往不能承受。当我们在解决一个问题时，我们选择的算法通常都需要是多项式级的复杂度，非多项式级的复杂度需要的时间太多，往往会超时，除非是数据规模非常小。

    自然地，人们会想到一个问题：会不会所有的问题都可以找到复杂度为多项式级的算法呢？很遗憾，答案是否定的。有些问题甚至根本不可能找到一个正确的算法来，这称之为“不可解问题”(Undecidable Decision Problem)。The Halting Problem就是一个著名的不可解问题，在我的Blog上有过专门的介绍和证明。再比如，输出从1到n这n个数的全排列。不管你用什么方法，你的复杂度都是阶乘级，因为你总得用阶乘级的时间打印出结果来。有人说，这样的“问题”不是一个“正规”的问题，正规的问题是让程序解决一个问题，输出一个“YES”或“NO”（这被称为判定性问题），或者一个什么什么的最优值（这被称为最优化问题）。那么，根据这个定义，我也能举出一个不大可能会有多项式级算法的问题来：Hamilton回路。问题是这样的：给你一个图，问你能否找到一条经过每个顶点一次且恰好一次（不遗漏也不重复）最后又走回来的路（满足这个条件的路径叫做Hamilton回路）。这个问题现在还没有找到多项式级的算法。事实上，这个问题就是我们后面要说的NPC问题。

    下面引入P类问题的概念：如果一个问题可以找到一个能在多项式的时间里解决它的算法，那么这个问题就属于P问题。P是英文单词多项式的第一个字母。哪些问题是P类问题呢？通常NOI和NOIP不会出不属于P类问题的题目。我们常见到的一些信息奥赛的题目都是P问题。道理很简单，一个用穷举换来的非多项式级时间的超时程序不会涵盖任何有价值的算法。
    接下来引入NP问题的概念。这个就有点难理解了，或者说容易理解错误。在这里强调（回到我竭力想澄清的误区上），NP问题不是非P类问题。NP问题是指可以在多项式的时间里验证一个解的问题。NP问题的另一个定义是，可以在多项式的时间里猜出一个解的问题。比方说，我RP很好，在程序中需要枚举时，我可以一猜一个准。现在某人拿到了一个求最短路径的问题，问从起点到终点是否有一条小于100个单位长度的路线。它根据数据画好了图，但怎么也算不出来，于是来问我：你看怎么选条路走得最少？我说，我RP很好，肯定能随便给你指条很短的路出来。然后我就胡乱画了几条线，说就这条吧。那人按我指的这条把权值加起来一看，嘿，神了，路径长度98，比100小。于是答案出来了，存在比100小的路径。别人会问他这题怎么做出来的，他就可以说，因为我找到了一个比100 小的解。在这个题中，找一个解很困难，但验证一个解很容易。验证一个解只需要O(n)的时间复杂度，也就是说我可以花O(n)的时间把我猜的路径的长度加出来。那么，只要我RP好，猜得准，我一定能在多项式的时间里解决这个问题。我猜到的方案总是最优的，不满足题意的方案也不会来骗我去选它。这就是NP问题。当然有不是NP问题的问题，即你猜到了解但是没用，因为你不能在多项式的时间里去验证它。下面我要举的例子是一个经典的例子，它指出了一个目前还没有办法在多项式的时间里验证一个解的问题。很显然，前面所说的Hamilton回路是NP问题，因为验证一条路是否恰好经过了每一个顶点非常容易。但我要把问题换成这样：试问一个图中是否不存在Hamilton回路。这样问题就没法在多项式的时间里进行验证了，因为除非你试过所有的路，否则你不敢断定它“没有Hamilton回路”。
    之所以要定义NP问题，是因为通常只有NP问题才可能找到多项式的算法。我们不会指望一个连多项式地验证一个解都不行的问题存在一个解决它的多项式级的算法。相信读者很快明白，信息学中的号称最困难的问题——“NP问题”，实际上是在探讨NP问题与P类问题的关系。

    很显然，所有的P类问题都是NP问题。也就是说，能多项式地解决一个问题，必然能多项式地验证一个问题的解——既然正解都出来了，验证任意给定的解也只需要比较一下就可以了。关键是，人们想知道，是否所有的NP问题都是P类问题。我们可以再用集合的观点来说明。如果把所有P类问题归为一个集合P中，把所有 NP问题划进另一个集合NP中，那么，显然有P属于NP。现在，所有对NP问题的研究都集中在一个问题上，即究竟是否有P=NP？通常所谓的“NP问题”，其实就一句话：证明或推翻P=NP。
    NP问题一直都是信息学的巅峰。巅峰，意即很引人注目但难以解决。在信息学研究中，这是一个耗费了很多时间和精力也没有解决的终极问题，好比物理学中的大统一和数学中的歌德巴赫猜想等。
    目前为止这个问题还“啃不动”。但是，一个总的趋势、一个大方向是有的。人们普遍认为，P=NP不成立，也就是说，多数人相信，存在至少一个不可能有多项式级复杂度的算法的NP问题。人们如此坚信P≠NP是有原因的，就是在研究NP问题的过程中找出了一类非常特殊的NP问题叫做NP-完全问题，也即所谓的 NPC问题。C是英文单词“完全”的第一个字母。正是NPC问题的存在，使人们相信P≠NP。下文将花大量篇幅介绍NPC问题，你从中可以体会到NPC问题使P=NP变得多么不可思议。


    为了说明NPC问题，我们先引入一个概念——约化(Reducibility，有的资料上叫“归约”)。
    简单地说，一个问题A可以约化为问题B的含义即是，可以用问题B的解法解决问题A，或者说，问题A可以“变成”问题B。《算法导论》上举了这么一个例子。比如说，现在有两个问题：求解一个一元一次方程和求解一个一元二次方程。那么我们说，前者可以约化为后者，意即知道如何解一个一元二次方程那么一定能解出一元一次方程。我们可以写出两个程序分别对应两个问题，那么我们能找到一个“规则”，按照这个规则把解一元一次方程程序的输入数据变一下，用在解一元二次方程的程序上，两个程序总能得到一样的结果。这个规则即是：两个方程的对应项系数不变，一元二次方程的二次项系数为0。按照这个规则把前一个问题转换成后一个问题，两个问题就等价了。同样地，我们可以说，Hamilton回路可以约化为TSP问题(Travelling Salesman Problem，旅行商问题)：在Hamilton回路问题中，两点相连即这两点距离为0，两点不直接相连则令其距离为1，于是问题转化为在TSP问题中，是否存在一条长为0的路径。Hamilton回路存在当且仅当TSP问题中存在长为0的回路。
    “问题A可约化为问题B”有一个重要的直观意义：B的时间复杂度高于或者等于A的时间复杂度。也就是说，问题A不比问题B难。这很容易理解。既然问题A能用问题B来解决，倘若B的时间复杂度比A的时间复杂度还低了，那A的算法就可以改进为B的算法，两者的时间复杂度还是相同。正如解一元二次方程比解一元一次方程难，因为解决前者的方法可以用来解决后者。
    很显然，约化具有一项重要的性质：约化具有传递性。如果问题A可约化为问题B，问题B可约化为问题C，则问题A一定可约化为问题C。这个道理非常简单，就不必阐述了。
    现在再来说一下约化的标准概念就不难理解了：如果能找到这样一个变化法则，对任意一个程序A的输入，都能按这个法则变换成程序B的输入，使两程序的输出相同，那么我们说，问题A可约化为问题B。
    当然，我们所说的“可约化”是指的可“多项式地”约化(Polynomial-time Reducible)，即变换输入的方法是能在多项式的时间里完成的。约化的过程只有用多项式的时间完成才有意义。

    好了，从约化的定义中我们看到，一个问题约化为另一个问题，时间复杂度增加了，问题的应用范围也增大了。通过对某些问题的不断约化，我们能够不断寻找复杂度更高，但应用范围更广的算法来代替复杂度虽然低，但只能用于很小的一类问题的算法。再回想前面讲的P和NP问题，联想起约化的传递性，自然地，我们会想问，如果不断地约化上去，不断找到能“通吃”若干小NP问题的一个稍复杂的大NP问题，那么最后是否有可能找到一个时间复杂度最高，并且能“通吃”所有的 NP问题的这样一个超级NP问题？答案居然是肯定的。也就是说，存在这样一个NP问题，所有的NP问题都可以约化成它。换句话说，只要解决了这个问题，那么所有的NP问题都解决了。这种问题的存在难以置信，并且更加不可思议的是，这种问题不只一个，它有很多个，它是一类问题。这一类问题就是传说中的NPC 问题，也就是NP-完全问题。NPC问题的出现使整个NP问题的研究得到了飞跃式的发展。我们有理由相信，NPC问题是最复杂的问题。再次回到全文开头，我们可以看到，人们想表达一个问题不存在多项式的高效算法时应该说它“属于NPC问题”。此时，我的目的终于达到了，我已经把NP问题和NPC问题区别开了。到此为止，本文已经写了近5000字了，我佩服你还能看到这里来，同时也佩服一下自己能写到这里来。

    NPC问题的定义非常简单。同时满足下面两个条件的问题就是NPC问题。首先，它得是一个NP问题；然后，所有的NP问题都可以约化到它。证明一个问题是 NPC问题也很简单。先证明它至少是一个NP问题，再证明其中一个已知的NPC问题能约化到它（由约化的传递性，则NPC问题定义的第二条也得以满足；至于第一个NPC问题是怎么来的，下文将介绍），这样就可以说它是NPC问题了。
    既然所有的NP问题都能约化成NPC问题，那么只要任意一个NPC问题找到了一个多项式的算法，那么所有的NP问题都能用这个算法解决了，NP也就等于P 了。因此，给NPC找一个多项式算法太不可思议了。因此，前文才说，“正是NPC问题的存在，使人们相信P≠NP”。我们可以就此直观地理解，NPC问题目前没有多项式的有效算法，只能用指数级甚至阶乘级复杂度的搜索。

    顺便讲一下NP-Hard问题。NP-Hard问题是这样一种问题，它满足NPC问题定义的第二条但不一定要满足第一条（就是说，NP-Hard问题要比 NPC问题的范围广）。NP-Hard问题同样难以找到多项式的算法，但它不列入我们的研究范围，因为它不一定是NP问题。即使NPC问题发现了多项式级的算法，NP-Hard问题有可能仍然无法得到多项式级的算法。事实上，由于NP-Hard放宽了限定条件，它将有可能比所有的NPC问题的时间复杂度更高从而更难以解决。

    不要以为NPC问题是一纸空谈。NPC问题是存在的。确实有这么一个非常具体的问题属于NPC问题。下文即将介绍它。
    下文即将介绍逻辑电路问题。这是第一个NPC问题。其它的NPC问题都是由这个问题约化而来的。因此，逻辑电路问题是NPC类问题的“鼻祖”。
    逻辑电路问题是指的这样一个问题：给定一个逻辑电路，问是否存在一种输入使输出为True。
    什么叫做逻辑电路呢？一个逻辑电路由若干个输入，一个输出，若干“逻辑门”和密密麻麻的线组成。看下面一例，不需要解释你马上就明白了。
  ┌───┐
  │ 输入1├─→┐    ┌──┐
  └───┘    └─→┤    │
                      │ or ├→─┐
  ┌───┐    ┌─→┤    │    │    ┌──┐
  │ 输入2├─→┤    └──┘    └─→┤    │
  └───┘    │                ┌─→┤AND ├──→输出
                └────────┘┌→┤    │
  ┌───┐    ┌──┐            │  └──┘
  │ 输入3├─→┤ NOT├─→────┘
  └───┘    └──┘
    这是个较简单的逻辑电路，当输入1、输入2、输入3分别为True、True、False或False、True、False时，输出为True。
    有输出无论如何都不可能为True的逻辑电路吗？有。下面就是一个简单的例子。
  ┌───┐
  │输入1 ├→─┐    ┌──┐
  └───┘    └─→┤    │
                      │AND ├─→┐
                ┌─→┤    │    │
                │    └──┘    │  ┌──┐
                │                └→┤    │
  ┌───┐    │                    │AND ├─→输出
  │输入2 ├→─┤  ┌──┐      ┌→┤    │
  └───┘    └→┤NOT ├→──┘  └──┘
                    └──┘
    上面这个逻辑电路中，无论输入是什么，输出都是False。我们就说，这个逻辑电路不存在使输出为True的一组输入。
    回到上文，给定一个逻辑电路，问是否存在一种输入使输出为True，这即逻辑电路问题。
    逻辑电路问题属于NPC问题。这是有严格证明的。它显然属于NP问题，并且可以直接证明所有的NP问题都可以约化到它（不要以为NP问题有无穷多个将给证明造成不可逾越的困难）。证明过程相当复杂，其大概意思是说任意一个NP问题的输入和输出都可以转换成逻辑电路的输入和输出（想想计算机内部也不过是一些 0和1的运算），因此对于一个NP问题来说，问题转化为了求出满足结果为True的一个输入（即一个可行解）。

    有了第一个NPC问题后，一大堆NPC问题就出现了，因为再证明一个新的NPC问题只需要将一个已知的NPC问题约化到它就行了。后来，Hamilton 回路成了NPC问题，TSP问题也成了NPC问题。现在被证明是NPC问题的有很多，任何一个找到了多项式算法的话所有的NP问题都可以完美解决了。因此说，正是因为NPC问题的存在，P=NP变得难以置信。P=NP问题还有许多有趣的东西，有待大家自己进一步的挖掘。攀登这个信息学的巅峰是我们这一代的终极目标。现在我们需要做的，至少是不要把概念弄混淆了。