它是正确的要求，解决一个NP完全问题在面试？ [英] Is it correct to ask to solve an NP-complete problem on a job interview?

问题描述

今天有一个<一个href="http://stackoverflow.com/questions/1720737/from-an-interview-removing-rows-and-columns-in-an-nn-matrix-to-maximize-the-sum">question在SO，在这里笔者是在接受记者采访时给出的NP完全问题，他显然没有被告知，这是其中之一。

Today there was a question on SO, where the author was given an NP-complete problem during an interview and he obviously hadn't been told that it was one.

什么问这些问题的目的是什么？并面试官期望什么样的行为，询问这样的事情是什么时候？证明？有用的启发？而且是它甚至有理由问一个，如果它不是一个众所周知的NP完全问题，每个人都应该知道的吗？ （有一个他们很多的）

What is the purpose of asking such questions? What behavior does the interviewer expect when asking such things? Proof? Useful heuristics? And is it even legitimate to ask one if it's not a well-known NP-complete problem everyone should know about? (there's a plenty of them)

推荐答案

完全合法的给我。如果你是计算机科学专业有很好的机会，你可以任一参数非正式为什么这个问题似乎很难，或（甚至更好），提供从已知的NP问题减少的草图。

Completely legitimate to me. If you are Computer Science professional there are good chances that you can either argument informally why the problem seems to be hard, or (even better) provide a sketch of reduction from a known NP-hard problem.

许多现实世界的问题，最终变成是NP难和计算器也有现在，然后对一个问题，原来是一个困难的复杂性问题（NP难，例如）。它是一个CS专业人员工具箱的一个重要组成部分，以便能够识别和主张这是众所周知的是困难的问题需要解决。

Many real world problems eventually turn out to be NP-hard, and stackoverflow also has now and then questions about the complexity of a problem which turns out to be a difficult one (NP-hard, for instance). It is an important part of a CS professionals toolbox to be able to recognize and to argue for problems which are known to be difficult to solve.

这篇关于它是正确的要求，解决一个NP完全问题在面试？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！