{"id":3526,"date":"2016-08-31T13:37:08","date_gmt":"2016-08-31T12:37:08","guid":{"rendered":"http:\/\/smart--grid.net\/?page_id=3526"},"modified":"2024-02-11T21:02:29","modified_gmt":"2024-02-11T20:02:29","slug":"problemes-industriels-et-reduction-polynomiale","status":"publish","type":"page","link":"https:\/\/complex-systems-ai.com\/es\/problemas-industriales-y-reduccion-de-polinomios\/","title":{"rendered":"Problemas industriales y reducci\u00f3n de polinomios 101."},"content":{"rendered":"<div data-elementor-type=\"wp-page\" data-elementor-id=\"3526\" class=\"elementor elementor-3526\">\n\t\t\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-2aee533 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"2aee533\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-33 elementor-top-column elementor-element elementor-element-2b32814\" data-id=\"2b32814\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-9898302 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"9898302\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"button.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<div class=\"elementor-button-wrapper\">\n\t\t\t\t\t<a class=\"elementor-button elementor-button-link elementor-size-sm\" href=\"https:\/\/complex-systems-ai.com\/es\/2020\/04\/03\/teorias-y-algoritmos-2\/\">\n\t\t\t\t\t\t<span class=\"elementor-button-content-wrapper\">\n\t\t\t\t\t\t\t\t\t<span class=\"elementor-button-text\">Teor\u00edas<\/span>\n\t\t\t\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t<div class=\"elementor-column elementor-col-33 elementor-top-column elementor-element elementor-element-42a195b\" data-id=\"42a195b\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-2d0896e elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"2d0896e\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"button.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<div class=\"elementor-button-wrapper\">\n\t\t\t\t\t<a class=\"elementor-button elementor-button-link elementor-size-sm\" href=\"https:\/\/complex-systems-ai.com\/es\/\">\n\t\t\t\t\t\t<span class=\"elementor-button-content-wrapper\">\n\t\t\t\t\t\t\t\t\t<span class=\"elementor-button-text\">Pagina de inicio<\/span>\n\t\t\t\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t<div class=\"elementor-column elementor-col-33 elementor-top-column elementor-element elementor-element-dcc1609\" data-id=\"dcc1609\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-8cb9d36 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"8cb9d36\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"button.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<div class=\"elementor-button-wrapper\">\n\t\t\t\t\t<a class=\"elementor-button elementor-button-link elementor-size-sm\" href=\"https:\/\/fr.wikipedia.org\/wiki\/R%C3%A9duction_polynomiale\" target=\"_blank\" rel=\"noopener\">\n\t\t\t\t\t\t<span class=\"elementor-button-content-wrapper\">\n\t\t\t\t\t\t\t\t\t<span class=\"elementor-button-text\">Wiki<\/span>\n\t\t\t\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-b9be8ed elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"b9be8ed\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-19171b6\" data-id=\"19171b6\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-e369a45 elementor-widget elementor-widget-toggle\" data-id=\"e369a45\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"toggle.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle-item\">\n\t\t\t\t\t<div id=\"elementor-tab-title-2381\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-2381\" aria-expanded=\"false\">\n\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon elementor-toggle-icon-left\" aria-hidden=\"true\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-closed\"><i class=\"fas fa-caret-right\"><\/i><\/span>\n\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-opened\"><i class=\"elementor-toggle-icon-opened fas fa-caret-up\"><\/i><\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t\t<\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t<a class=\"elementor-toggle-title\" tabindex=\"0\">I. Reducci\u00f3n y presentaci\u00f3n de los 21 problemas de Karp<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-2381\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-2381\"><ul>\n<li>Satisfacci\u00f3n\n<ul>\n<li>Hacer clic\n<ul>\n<li>Establecer embalaje<\/li>\n<li>Cubierta de v\u00e9rtice\n<ul>\n<li>Establecer cubierta<\/li>\n<li>Conjunto de arco de retroalimentaci\u00f3n<\/li>\n<li>Conjunto de nodos de comentarios<\/li>\n<li>Circuito hamiltoniano dirigido\n<ul>\n<li>Circuito hamiltoniano no dirigido<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<\/li>\n<li>Programaci\u00f3n de n\u00fameros enteros 0-1<\/li>\n<li>3-SAT\n<ul>\n<li>N\u00famero crom\u00e1tico\n<ul>\n<li>Haga clic en la portada<\/li>\n<li>Cobertura exacta\n<ul>\n<li>Coincidencia 3D<\/li>\n<li>\u00c1rbol de Steiner<\/li>\n<li>Golpeando el set<\/li>\n<li><a href=\"https:\/\/complex-systems-ai.com\/es\/problemas-industriales-y-reduccion-de-polinomios\/problema-de-la-mochila\/\">Mochila<\/a>\n<ul>\n<li>Secuencia de trabajos<\/li>\n<li>Dividir\n<ul>\n<li>Max-corte<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<\/li>\n<\/ul><\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-5475587f elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"5475587f\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-68ce53ae\" data-id=\"68ce53ae\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-eb06a09 elementor-widget elementor-widget-text-editor\" data-id=\"eb06a09\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<p><\/p>\n<div id=\"ez-toc-container\" class=\"ez-toc-v2_0_82_2 counter-hierarchy ez-toc-counter ez-toc-grey ez-toc-container-direction\">\n<div class=\"ez-toc-title-container\">\n<p class=\"ez-toc-title\" style=\"cursor:inherit\">Contenido<\/p>\n<span class=\"ez-toc-title-toggle\"><a href=\"#\" class=\"ez-toc-pull-right ez-toc-btn ez-toc-btn-xs ez-toc-btn-default ez-toc-toggle\" aria-label=\"Tabla de contenido alternativo\"><span class=\"ez-toc-js-icon-con\"><span class=\"\"><span class=\"eztoc-hide\" style=\"display:none;\">Palanca<\/span><span class=\"ez-toc-icon-toggle-span\"><svg style=\"fill: #999;color:#999\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" class=\"list-377408\" width=\"20px\" height=\"20px\" viewbox=\"0 0 24 24\" fill=\"none\"><path d=\"M6 6H4v2h2V6zm14 0H8v2h12V6zM4 11h2v2H4v-2zm16 0H8v2h12v-2zM4 16h2v2H4v-2zm16 0H8v2h12v-2z\" fill=\"currentColor\"><\/path><\/svg><svg style=\"fill: #999;color:#999\" class=\"arrow-unsorted-368013\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"10px\" height=\"10px\" viewbox=\"0 0 24 24\" version=\"1.2\" baseprofile=\"tiny\"><path d=\"M18.2 9.3l-6.2-6.3-6.2 6.3c-.2.2-.3.4-.3.7s.1.5.3.7c.2.2.4.3.7.3h11c.3 0 .5-.1.7-.3.2-.2.3-.5.3-.7s-.1-.5-.3-.7zM5.8 14.7l6.2 6.3 6.2-6.3c.2-.2.3-.5.3-.7s-.1-.5-.3-.7c-.2-.2-.4-.3-.7-.3h-11c-.3 0-.5.1-.7.3-.2.2-.3.5-.3.7s.1.5.3.7z\"\/><\/svg><\/span><\/span><\/span><\/a><\/span><\/div>\n<nav><ul class='ez-toc-list ez-toc-list-level-1' ><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-1\" href=\"https:\/\/complex-systems-ai.com\/es\/problemas-industriales-y-reduccion-de-polinomios\/#Reduction-polynomiale\" >Reducci\u00f3n de polinomios<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-2\" href=\"https:\/\/complex-systems-ai.com\/es\/problemas-industriales-y-reduccion-de-polinomios\/#Complexite-polynomiale\" >Complejidad polinomial<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-3\" href=\"https:\/\/complex-systems-ai.com\/es\/problemas-industriales-y-reduccion-de-polinomios\/#Reduction-polynomiale-2\" >Reducci\u00f3n de polinomios<\/a><\/li><\/ul><\/nav><\/div>\n<h2><span class=\"ez-toc-section\" id=\"Reduction-polynomiale\"><\/span>Reducci\u00f3n de polinomios<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p>Los problemas de la investigaci\u00f3n operativa, y m\u00e1s en general de soporte de decisiones suelen ser Np-completos, es decir que no conocemos algoritmos que permitan encontrar una soluci\u00f3n \u00f3ptima en tiempo polinomial, pero sabemos c\u00f3mo obtener una soluci\u00f3n factible en polinomio. tiempo (por reducci\u00f3n polinomial).<\/p>\n<p><\/p>\n<p><\/p>\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Complexite-polynomiale\"><\/span>Complejidad polinomial<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p><\/p>\n<p><\/p>\n<div style=\"padding: 5px; background-color: #d5edff; border: 2px solid #3c95e8; -moz-border-radius: 9px; -khtml-border-radius: 9px; -webkit-border-radius: 9px; border-radius: 9px;\">Los problemas son decidibles, es decir, el problema se puede formular de tal manera que la respuesta sea S\u00ed o No. La complejidad de sus problemas se considerar\u00e1 en el peor de los casos.<\/div>\n<p><\/p>\n<p><\/p>\n<p>a <a href=\"https:\/\/complex-systems-ai.com\/es\/algoritmico\/\">algoritmo<\/a> es de complejidad polinomial si existe un polinomio P tal que el n\u00famero de instrucciones elementales realizadas durante su ejecuci\u00f3n en una instancia de tama\u00f1o n es como m\u00e1ximo P(n). Un problema es de complejidad polinomial si existe un algoritmo de complejidad polinomial que lo resuelve. Es importante recalcar que la representaci\u00f3n de las estructuras de datos utilizadas no influye en la complejidad.<\/p>\n<p><\/p>\n<p><\/p>\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Reduction-polynomiale-2\"><\/span>Reducci\u00f3n de polinomios<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p><\/p>\n<p><\/p>\n<p>Un problema de decisi\u00f3n P se reduce a un problema de decisi\u00f3n P &#039;si existe un algoritmo polinomial R que transforma cualquier entrada u de P en una entrada u&#039; = R (u) de P &#039;tal que u\u2208S\u00ed (P) \u21d4 u&#039;\u2208 Si p &#039;).<\/p>\n<p><\/p>\n<p><\/p>\n<figure class=\"wp-block-image size-large\"><img fetchpriority=\"high\" decoding=\"async\" class=\"alignnone wp-image-3565 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/reduc.png\" alt=\"reducci\u00f3n de polinomios 21 problemas de karp\" width=\"814\" height=\"278\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/reduc.png 814w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/reduc-300x102.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/reduc-768x262.png 768w\" sizes=\"(max-width: 814px) 100vw, 814px\" \/><\/figure>\n<p><\/p>\n<p><\/p>\n<p>Esto sugiere la siguiente implicaci\u00f3n: si hay un algoritmo polinomial para P &#039;, tambi\u00e9n hay uno para P.<\/p>\n<p><\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<\/div>","protected":false},"excerpt":{"rendered":"<p>Teor\u00edas Home page Wiki I. Reducci\u00f3n y presentaci\u00f3n de los 21 problemas de Karp Satisfiability Clique Set packing Vertex cover Set covering Feedback arc set Feedback \u2026 <\/p>","protected":false},"author":1,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-3526","page","type-page","status-publish","hentry"],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/3526","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/comments?post=3526"}],"version-history":[{"count":22,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/3526\/revisions"}],"predecessor-version":[{"id":20455,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/3526\/revisions\/20455"}],"wp:attachment":[{"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/media?parent=3526"}],"curies":[{"name":"gracias","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}