Me pidieron que resolviera un conocido problema de NP completo en una entrevista. ¿Debería negarme a resolverlo?

Hice entrevistas en Microsoft y luego en Amazon durante unos 20 años. Si un solicitante dijera “Es NP completo”, diría “sí, pero aún tenemos que hacer algo. ¿Qué hacemos?” Renunciar es un no-contrato automático.

En el mundo real, a menudo tenemos que lidiar con problemas de NP completo y, a diferencia de lo que todos parecen decir, no podemos aceptar soluciones que a veces toman un tiempo exponencial. En cambio, aceptamos soluciones que a veces son subóptimas. El problema del vendedor ambulante, por ejemplo, puede ser aproximado encontrando un camino “suficientemente bueno”, incluso si no siempre es óptimo. O para 3-SAT, simplemente limite el tiempo dedicado a buscar una solución y acepte que el algoritmo fallará el 1% del tiempo.

Piense en esta pregunta como una prueba para determinar si el solicitante puede manejar una situación en la que no es posible una respuesta perfecta. Una solución suficientemente buena satisface esta pregunta. Los puntos adicionales van a la persona que muestra que realmente es NP-complete. Puntos extra por preguntar explícitamente “¿cuánto error es aceptable?” O al menos para pensar en cómo “relajar” el problema. Doble bonificación si solicita más información sobre cómo las fallas afectarán a los clientes.

Ahora, si el entrevistador dice “cero error es aceptable”, entonces continúe y codifique una solución de tiempo exponencial. Pero si lo hacen, entonces puede que no sea el tipo de empresa en la que desea trabajar.

Debe mencionar que el problema parece ser NP completo y por qué, y profundizar en los parámetros bajo los cuales se requiere ejecutar la solución. Puntos de bonificación por decir que si tuviera que resolverlo en el lugar de trabajo, verificaría para encontrar los enfoques más eficientes ideados hasta ahora.

A pesar de ser generalmente costoso de ejecutar, si N es muy pequeño, estos problemas pueden ser forzados por la fuerza bruta y proporcionar una funcionalidad útil.

La entrevista no se trata solo de obtener la respuesta correcta. Se trata de cómo llegar allí, su pensamiento interrogativo para comprender los parámetros del problema, su resolución de problemas y su comportamiento general. Se trata de cómo enfrenta un desafío, especialmente cuando sabe que el problema está plagado de peligros como la intratabilidad.

Negarme a resolverlo o incluso mordisquear los bordes no sería una contratación para mí, incluso para un recién graduado de la universidad.

Depende del problema. Algunos problemas tienen buenas aproximaciones, algunos problemas se pueden resolver fácilmente para cualquier estructura y tamaño de entrada práctica.

Por ejemplo, los solucionadores SAT pueden resolver un CNF con un millón de variables y cientos de miles de cláusulas (e incluso más). Muchos problemas prácticos NP-hard se pueden resolver con un solucionador SAT moderno. Muchos problemas pueden reducirse a CNF y resolverse con un solucionador SAT razonablemente rápido, ¿y tal vez esto es lo que querían?

Siempre tenga en cuenta que hay una gran diferencia entre la teoría y la práctica. Por ejemplo, en teoría, el algoritmo Simplex es exponencial, pero en la práctica supera a los algoritmos polinomiales, como el método de punto Interior, en la mayoría de los casos. Esto se debe a que el comportamiento exponencial ocurre solo en estructuras de entrada relativamente poco comunes.

Conocer la teoría es genial cuando te avanza, nunca hagas que te ensille.

En general, no, no debes rechazar; deberías resolverlo. Pero en general, también debe explicar los problemas con este enfoque, y debe discutir con el entrevistador si se espera que proporcione una solución matemáticamente correcta y necesariamente lenta, o una buena solución heurística que no garantice que produzca la respuesta correcta – como la construcción de un algoritmo genético. Para muchos (pero no todos) problemas de NP completo, existen soluciones heurísticas que generan resultados razonablemente buenos con una probabilidad razonablemente alta, y en la vida real, esto es a menudo (pero no siempre) lo suficientemente bueno. Esto sucede con tanta frecuencia que tiene sentido preguntar estas cosas en una entrevista de codificación.

Definitivamente no. Eso resultaría en una inmediata no contratación.

Lo que buscaría en un candidato es la capacidad de atacar problemas difíciles a pesar de su dificultad. Es la voluntad de tratar de encontrar una solución a pesar de las limitaciones que es la marca de un gran candidato. A menudo, los grandes candidatos se apasionan por resolver el problema, especialmente cuando es tan difícil.

Si las restricciones resultan demasiado difíciles, entonces siga el ejemplo del Capitán James T. Kirk del Star Trek original cuando se enfrente con la prueba de Kobayashi Maru sin ganar: redefinir el problema.

Algunas formas de hacer esto:

• ¿Qué supuestos entraron en este problema?
• ¿Alguno de estos supuestos es incorrecto?
• ¿Alguna de las entradas de prueba está defectuosa?
• ¿Alguna de las restricciones no es firme?
• ¿Alguna de las limitaciones se puede evitar mediante la inversión en un recurso alternativo?
• ¿Podríamos reducir esto a un problema más simple?
• ¿Podríamos resolver un problema completamente diferente que cumpliría los objetivos?
• ¿Podríamos resolver esto usando una heurística probabilística?

Tal vez de los problemas importantes que enfrenta una empresa simplemente no se han hecho antes. Desea dar la percepción como una de esas personas que pueden resolver los problemas más difíciles de la organización sin importar cuáles sean.

Probablemente fallaría en la entrevista si simplemente se negara a resolver el problema que le dieron.

Parece haber cierta confusión sobre los problemas de NP-Complete.

Los problemas de NP-Complete no son irresolubles . Simplemente no se pueden resolver en tiempo polinómico , lo que significa que para conjuntos de datos muy grandes la solución puede tomar mucho tiempo para computarse.

Lo que buscan los entrevistadores es que reconozca qué problema de NP-Complete le dieron e identifique el algoritmo correcto que debe aplicar al problema. Probablemente con puntos de bonificación para profundizar en los requisitos específicos y ofrecer sugerencias de modificaciones a los algoritmos estándar para optimizar aún más el problema específico.

Esta idea es completamente absurda, como si los problemas NP completos fueran alguna clase de problemas “injustos” o “irrazonables”. Desafortunadamente, la naturaleza no siempre funciona como deseamos los humanos arrogantes … Deberías estar agradecido de que nuestra teoría nos permita reconocer tal problema y seguir adelante usando las técnicas que tuvimos la suerte de descubrir. Los problemas de NP completo son simplemente complejos, no irresolubles. Pero sí, por supuesto, cuando profundizas en eso, comienzas a encontrarte con esos problemas locos que no pueden ser probados, etc., pero esa es otra historia …

En una entrevista, si puede identificar la complejidad del problema, dígalo y haga lo mejor que pueda. Probablemente podrá aplicar la búsqueda de profundidad primero. Si puede demostrar que encontrará la solución, eso ya es genial. Si también puedes encontrar una buena heurística, ¡genial!

Recomiendo conocer muy bien los problemas de la mochila (no siempre NP-completo, como el problema de programación de enfermeras también iirc). También familiarícese con el TSP, SAT, Programación de enteros … Entonces quizás aprenda algo sobre metaheurística. GA, Tabu-search, lo que sea … dudo que muchas entrevistas de codificación realmente entren en ese tipo de cosas, es un área especializada.

Asegúrese de tener una buena comprensión de BFS, DFS y A *. Por lo general, las partes más interesantes de las entrevistas son solo sobre programación dinámica y estructuras de datos basadas en árboles.

De todos modos, nunca “se niegue” a hacer nada en una entrevista. El entrevistado no está allí para engañarte ni nada, quiere comprender tu conocimiento y especialmente tu personalidad … Alguien se niega a hacer algo que te pido en una entrevista, lo más probable es que me decida de inmediato.

Nunca te niegues a resolver un problema en una entrevista. En el peor de los casos, solo lo resuelve de una manera ingenua / ineficiente (fuerza bruta).

Si conoce mejores formas, hable sobre ellas. Por lo general, hay algunos, como se ha mencionado sobre el problema de la mochila (además, hay muchos problemas que se pueden aproximar utilizando la heurística correcta).

No sé sobre su entrevistador en particular, pero si estaba entrevistando a un candidato, y él / ella me dijo que el problema es NP-complete, y proporcionó la implementación de un algoritmo que hizo uso de la heurística (o programación dinámica) o proporcionó a ambos una prueba de que es de hecho NP-completa por reducción, y al menos fuerza bruta / implementación ingenua, le daría los puntos con seguridad de cualquier manera.

La diferencia entre un problema de NP completo y un problema con una solución eficiente a veces puede ser muy sutil. Como en cualquier momento en el que no esté seguro en una entrevista, debe hacer una pregunta aclaratoria. Algo así como “eso suena como 3SAT. ¿Estás buscando una heurística o aproximación, o me estoy perdiendo algo?” debería hacer.

A menudo le pido a la gente que resuelva un problema que es NP-hard en la codificación de entrevistas, pero restringido a un dominio que lo hace solucionable. Por ejemplo, podría pedirle a alguien que resuelva la cubierta del vértice en un gráfico bipartito (aunque generalmente no le pregunto a uno tan difícil).

Qué..? No..

Un problema con NP-completo no significa que no se pueda resolver (solo los problemas sin solución son irresolubles). Ser NP-complete / NP-hard solo significa que no hay soluciones generales conocidas públicamente:

1. que se ejecutan de manera eficiente (es decir, en el tiempo polinomio en el orden del tamaño de entrada)
2. por clases de máquinas informáticas que generalmente existen y están disponibles (es decir, máquinas deterministas de Turing).

Como han dicho los otros encuestados, hay varias soluciones que cualquier persona familiarizada con los problemas NP-hard debería conocer y estar listo para ofrecer:

1. soluciones generales que son correctas / óptimas pero ineficientes.
2. soluciones no generales que explotan aspectos del problema específico, como un tamaño de entrada considerablemente pequeño o el uso de heurísticas adecuadas para el problema específico.
3. soluciones generales que no son óptimas pero que se aproximan dentro de un límite de error aceptable.

La inteligencia artificial se ocupa en gran medida de encontrar soluciones viables para muchos problemas NP-difíciles y estos actualmente tienen demanda en la industria del software. Si se plantea un problema de este tipo durante una entrevista, negarse a resolverlo es admitir la falta de familiaridad con estos temas de CS y es muy probable que se retire de la consideración del puesto.

No, muchos algoritmos NP-complete están realmente resueltos para todos los propósitos. Muchos problemas en el enrutamiento de Internet son NP-hard / complete, pero obviamente se ha ampliado a miles de millones de usuarios. Del mismo modo, el transistor place-and-route es NP-complete, pero obviamente las empresas han diseñado procesadores informáticos muy eficientes con miles de millones de transistores.

Probablemente deberías decir que el problema es NP-completo, probarlo y proponer una heurística que creas que proporcionará una solución decente. Sugerencia: las soluciones codiciosas generalmente funcionan bastante bien.

Mi enfoque para tal pregunta sería doble.

1. Vuelva a leer / aclarar lo que la pregunta realmente quiere que envíe. Por ejemplo, encontrar un camino hamiltoniano en un gráfico dirigido dado es un problema NP completo bien conocido. Sin embargo, si la pregunta es decidir si el gráfico tiene una ruta hamiltoniana entre dos vértices especificados, entonces se puede resolver.
   Tenga en cuenta la diferencia entre encontrar una ruta o simplemente descubrir si existe dicha ruta. La última pregunta puede resolverse en [matemática] O (2 ^ n. P (n)) [/ matemática] donde [matemática] p (n) [/ matemática] es una función polinómica de [matemática] n [/ matemática] .
2. Trate de encontrar un algoritmo de aproximación para el problema completo de NP.
   Muchos problemas completos de NP tienen aproximaciones decentes que garantizan un buen límite en la solución. Por ejemplo, el problema de cobertura mínima de vértice ponderado tiene un algoritmo de aproximación de 2 factores, donde la solución de aproximación está garantizada dentro de los límites de la solución óptima 2 *.

Depende del contexto. En primer lugar, identificar un problema de NP completo es algo bueno, pero no es necesario cruzar las manos.

Uno puede probar un algoritmo aproximado, después de mencionar que el problema exacto es NP-C. Esto sucede todo el tiempo en muchos dominios. Si está entrevistando para algún trabajo, incluso remotamente relacionado con la investigación de operaciones, lo más probable es que, literalmente, cada problema que resolverá será difícil. Los ejemplos pueden variar desde la programación hasta los recorridos.

Diría que el mejor enfoque será identificar subestructuras combinatorias bien conocidas en el problema, y ​​reducirlo a una incrustación que tenga un procedimiento de resolución aproximado basado en principios. Por ejemplo, puede reducir el problema a alguna partición o estructura de programación entera, en cuyo punto puede detenerse.

Creo que lo único que falta en las respuestas es la reducción del algoritmo.

Para obtener la puntuación perfecta, lo ideal es demostrar que es NP-Complete al encontrar una manera de reducirlo en tiempo polinómico a otro problema NP-Complete.

No puedo encontrar un algoritmo eficiente, pero tampoco todas estas personas famosas.

Luego, puede continuar preguntándoles qué quieren.

Proceda con una aproximación suficientemente buena para grandes conjuntos de datos, o encuentre una solución lo suficientemente buena solo para conjuntos pequeños. Posiblemente use programación dinámica.

PD: nunca entendí cómo funcionan exactamente las reducciones de algoritmos. Espero que algún día tenga tiempo de volver a visitar CLRS.

Lamento si esto puede sonar duro para usted y la audiencia, y estoy seguro de que es totalmente acertado, pero la forma en que formuló su pregunta realmente lo hizo sonar como un friki autista que ve lo que ha aprendido en las clases de CS como conocimiento divino . Puede impresionar a su entrevistador al saber que es NP completo, pero un candidato que se niegue a resolverlo me parecerá absolutamente inútil.

Debe comprender que las empresas comerciales contratan desarrolladores para resolver problemas, y todos los problemas tienen una solución, ya sea a veces parcial o ineficiente. El propósito de resolver estos problemas no es colgarlo en algún salón de la fama de los “problemas difíciles que resolvió”.

El propósito es acercar a la empresa a su objetivo, ya sea facilitando operaciones, aumentando las ventas o haciendo que el producto sea más atractivo para los clientes (aumentando así las ventas). En todos los casos, el objetivo es mejorar el resultado final de la empresa a largo plazo.

Si piensas en el problema de que Netflix intenta crear un buen algoritmo de recomendación de películas, te darás cuenta de que no existe un algoritmo perfecto. Sin embargo, hacer que el algoritmo sugiera cosas y permitir que las personas ayuden a Netflix a refinar el algoritmo gracias a sus comentarios después de haber visto una película recomendada, es ciertamente beneficioso para la experiencia del usuario y, como resultado, para el resultado final de Netflix

Un montón de buenos consejos aquí. Además, le sugiero que eche un vistazo a este artículo bastante conocido e influyente sobre la complejidad computacional:

“Donde están los problemas realmente difíciles” de Cheeseman, Kanefsky y Taylor
en Actas de la Duodécima Conferencia Internacional sobre Inteligencia Artificial (1991): IJCAI 87 (enlace al documento en PDF está aproximadamente un 60% más abajo en la página)

Ya en 1991 podían comenzar su trabajo con la observación: “Es bien sabido que para muchos problemas con NP completo, como K-Sat, etc., los casos típicos son fáciles de resolver; por lo tanto, los casos computacionalmente difíciles deben ser raros ( suponiendo P = NP) “. El documento luego proporciona una idea de lo que hace que los casos realmente difíciles sean difíciles. Sus entrevistadores podrían estar impresionados si estuviera familiarizado con estas ideas y no se sintieran intimidados por los teoremas sobre los peores casos. Alternativamente, ¡pueden esperar que sepas sobre esto!

La pregunta tiene dos razones para hacerse. Primero, el entrevistador quiere verificar que comprenda el concepto de integridad de NP y, por lo tanto, no se sentará y hackeará una solución incorrecta que se ejecuta en tiempo P. En segundo lugar, el entrevistador quiere ver cómo maneja los problemas computacionalmente difíciles: ¿los fuerza por fuerza bruta, o intenta limitar el espacio del problema, o ambos? Muchos problemas informáticos comunes son NP-completos, pero las personas los resuelven (o subconjuntos frecuentes de problemas) todo el tiempo. Demuestra que puedes hacer ambas cosas.

No. Debe reconocer que este problema se encuentra en una clase especial donde las soluciones “buenas” son desconocidas y probablemente no existen, pero por razones prácticas necesitamos “alguna” solución. Y debido a la naturaleza traidora de estos problemas, presentan un rico espacio comercial. Muchas veces, un pequeño rendimiento está disponible a un gran costo. Si solo va a usar la solución una vez, como enrutar un camión de reparto, entonces probablemente sea mejor vivir con un poco de ineficiencia en la solución, pero si está usando la solución muchas veces, como un programa de perforación para un placa de circuito, entonces probablemente será mejor servido gastando el tiempo de cálculo adicional. Y reconozca que evaluar estos espacios comerciales requiere no solo facilidad con soluciones sino también sabiduría en el dominio del problema. Además, si el entrevistador exhibe una sana curiosidad, puede observar que no todos los problemas de NP-Complete se crean por igual, y que el conjunto de tales problemas es realmente una clase de equivalencia de los peores casos patológicos. En algunos de estos problemas (p. Ej., Suma de subconjuntos) casi siempre puede obtener una respuesta absoluta. En otros casos, como el problema del vendedor ambulante euclidiano, existen heurísticas que garantizan que obtendrá una solución no peor que 1 + x de la mejor solución (donde x define ese espacio comercial de costo / rendimiento), y en otros casos, como la Galería de arte Problema: se puede demostrar que no hay heurísticas bien delimitadas. Si puede lograr que el entrevistador llegue a ese punto, ha comenzado una conversación interesante que valdrá la pena si obtiene el trabajo o no.

No, a veces los problemas se pueden resolver en una entrevista a pesar de que son NP completos. Por ejemplo, el problema de la mochila es NP-completo, pero tiene una solución de programación dinámica que se ejecuta en tiempo O (nW), donde n es el número de elementos y W es la capacidad de carga de la mochila.

La razón por la que esto no cuenta como tiempo polinómico es que el argumento W toma bits de registro W para representar, y las complejidades de tiempo se miden en relación con el número de bits en la entrada, no su valor numérico. Pero para muchas aplicaciones, el “tiempo pseudopolinomial” es lo suficientemente bueno, y definitivamente debería poder codificar la solución de programación dinámica en una entrevista.