检索结果-内蒙古大学图书馆

On the computational complexity of finding hard tautologies

BULLETIN OF THE LONDON MATHEMATICAL SOCIETY 2014年第1期46卷 111-125页

作者： Krajicek, Jan Charles Univ Prague Dept Algebra Fac Math & Phys Prague 186 75 8 Czech Republic

It is well known (cf. Krajicek and Pudlak ['Propositional proof systems, the consistency of first order theories and the complexity of computations', J. Symbolic Logic 54 (1989) 1063-1079]) that a polynomial time algorithm finding tautologies hard for a propositional proof system P exists if and only if P is not optimal. Such an algorithm takes 1((k)) and outputs a tautology tau(k) of size at least k such that P is not p-bounded on the set of all formulas tau(k). We consider two more general search problems involving finding a hard formula, Cert and Find, motivated by two hypothetical situations: that one can prove that NP not equal coNP and that no optimal proof system exists. In Cert one is asked to find a witness that a given non-deterministic circuit with k inputs does not define TAUT boolean AND{0, 1}(k). In Find, given 1((k)) and a tautology alpha of size at most k(0)(c), one should output a size k tautology beta that has no size k(1)(c) P-proof from substitution instances of alpha. We will prove, assuming the existence of an exponentially hard one-way permutation, that Cert cannot be solved by a time 2(O(k)) algorithm. Using a stronger hypothesis about the proof complexity of the Nisan-Wigderson generator, we show that both problems Cert and Find are actually only partially defined for infinitely many k (that is, there are inputs corresponding to k for which the problem has no solution). The results are based on interpreting the Nisan-Wigderson generator as a proof system.

关键词： COMPUTATIONAL complexity PLEONASM MATHEMATICAL proofs SYMBOLIC & mathematical logic polynomial time algorithms algorithms EXISTENCE theorems

来源：评论

学校读者我要写书评

暂无评论

Faster algorithms for the quickest transshipment problem

引用

SIAM JOURNAL ON OPTIMIZATION 2001年第1期12卷 18-35页

作者： Fleischer, LK Carnegie Mellon Univ Grad Sch Ind Adm Pittsburgh PA 15213 USA

A transshipment problem with demands that exceed network capacity can be solved by sending flow in several waves. How can this be done in the minimum number of waves? This is the question tackled in the quickest transshipment problem. Hoppe and Tardos [Math. Oper. Res., 25 (2000), pp. 36-62] describe the only known polynomial time algorithm to solve this problem. They actually solve the significantly harder problem in which it takes a prespecified amount of time for flow to travel from one end of an arc to the other. Their algorithm repeatedly calls an oracle for submodular function minimization. We present an algorithm that finds a quickest transshipment with a polynomial number of maximum flow computations, and a faster algorithm that also uses minimum cost flow computations. When there is only one sink, we show how the algorithm can be sped up to return a solution using O(k) maximum flow computations, where k is the number of sources. Hajek and Ogier [Networks, 14 (1984), pp. 457-487] describe an algorithm that finds a fractional solution to the single sink quickest transshipment problem on a network with n nodes and m arcs using O(n) maximum flow computations. They actually solve the universally quickest transshipment a flow over time that minimizes the amount of supply left in the network at every moment of time. In this paper, we show how to solve the universally quickest transshipment in O(mn log(n(2)/m)) time, the same asymptotic time as a push-relabel maximum flow computation.

关键词： dynamic network flows transshipment problem parametric flow polynomial time algorithms

来源：评论

学校读者我要写书评

暂无评论

Decomposing plane cubic graphs

引用

EUROPEAN JOURNAL OF COMBINATORICS 2016年第PartA期52卷 40-46页

作者： Ozeki, Kenta Ye, Dong Natl Inst Informat Chiyoda Ku Tokyo 1018430 Japan JST ERATO Kawarabayashi Large Graph Project Tokyo Japan Middle Tennessee State Univ Dept Math Sci Murfreesboro TN 37132 USA Middle Tennessee State Univ Ctr Computat Sci Murfreesboro TN 37132 USA

It was conjectured by Hoffmann-Ostenhof that the edge set of every cubic graph can be decomposed into a spanning tree, a matching and a family of cycles. We prove the conjecture for 3-connected cubic plane graphs and 3-connected cubic graphs on the projective plane. Our proof provides a polynomial time algorithm to find the decomposition for 3-connected cubic plane graphs. (C) 2015 Elsevier Ltd. All rights reserved.

关键词： GRAPH connectivity DECOMPOSITION (Mathematics) EDGES (Geometry) SPANNING trees (Graph theory) MATCHING theory polynomial time algorithms

来源：评论

学校读者我要写书评

暂无评论

Blenders in centre unstable Henon-like families: with an application to heterodimensional bifurcations

引用

NONLINEARITY 2014年第3期27卷 353-378页

作者： Diaz, Lorenzo J. Kiriki, Shin Shinohara, Katsutoshi Pontificia Univ Catolica Rio de Janeiro Depto Matemat BR-22453900 Rio de Janeiro RJ Brazil Tokai Univ Dept Math Hiratsuka Kanagawa 2591292 Japan Univ Tokyo Inst Ind Sci Aihara Innovat Math Modelling Project FIRSTMeguro Ku Tokyo 1538505 Japan

We give an explicit family of polynomial maps called centre unstable Henon-like maps and prove that they exhibit blenders for some parameter values. Using this family, we also prove the occurrence of blenders near certain non-transverse heterodimensional cycles under high regularity assumptions. The proof involves a renormalization scheme along heteroclinic orbits. We also investigate the connection between the blender and the original heterodimensional cycle.

关键词： BIFURCATION theory polynomial time algorithms ORBITS RENORMALIZATION group NONLINEAR differential equations -- Numerical solutions polynomialS

来源：评论

学校读者我要写书评

暂无评论

GROUP CENTER AND GROUP MEDIAN OF A TREE

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 1993年第3期65卷 400-406页

作者： GUPTA, SK PUNNEN, AP UNIV WINDSOR FAC BUSINESS ADMWINDSOR N9B 3P4ONTARIOCANADA INDIAN INST TECHNOL DEPT ANIM RESKANPUR 208016UTTAR PRADESHINDIA

We consider the problem of identifying group centre and group median of a tree. algorithms are presented that are better than the available algorithms which solve these problems on general networks. For the group median problem, an alternate approach is suggested which runs in linear time on specially structured problems. Properties of the set of all optimal solutions of these problems are also investigated.

关键词： LOCATION NETWORKS CENTER MEDIAN polynomial time algorithms

来源：评论

学校读者我要写书评

暂无评论

Two-Agent Single-Machine Scheduling with Resource-Dependent Starting times

引用

MATHEMATICAL PROBLEMS IN ENGINEERING 2013年第1期2013卷 1-5页

作者： Liu, Peng Tian, Xiaoyu Shenyang Univ Technol Sch Management Shenyang 110870 Peoples R China

We consider several two-agent scheduling problems with resource consumption on a single machine, where each of the agents wants to minimize a measure dependent on its own jobs. The starting time of each job of the first agent is related to the amount of resource consumed. The objective is to minimize the total amount of resource consumption of the first agent with the restriction that the makespan or the total completion time of the second agent cannot exceed a given bound U. The optimal properties and the optimal polynomial time algorithms are proposed to solve the scheduling problems.

关键词： MACHINE theory COMPUTER scheduling RESOURCE dependence theory ENERGY consumption polynomial time algorithms BOUNDS (Mathematics)

来源：评论

学校读者我要写书评

暂无评论

Two equivalent measures on weighted hypergraphs

引用

DISCRETE APPLIED MATHEMATICS 2006年第16期154卷 2330-2334页

作者： Ito, Hiro Nagamochi, Hiroshi Kyoto Univ Sch Informat Dept Commun & Comp Engn Kyoto 6068501 Japan Kyoto Univ Sch Informat Dept Appl Math & Phys Kyoto 6068501 Japan

Let H = (N, E, w) be a hypergraph with a node set N = {0, 1, n - 1}, a hyperedge set E subset of 2(N), and real edge-weights w(e) for e E E. Given a convex n-gon P in the plane with vertices x(0), x(1),..., x(n-1) which are arranged in this order clockwisely, let each node i E N correspond to the vertex xi and define the area A(P)(H) of H on P by the sum of the weighted areas of convex hulls for all hyperedges in H. For 0 <= i < J < k <= n - 1, a convex three-cut C(i,j, k) of N is {(i,..., j - 1}, {j,..., k - 1}, (k,..., n - 1, 0,..., i - 1)) and its size c(H)(i,j, k) in H is defined as the sum of weights of edges e is an element of E such that e contains at least one node from each of {i,..., j - 1}, {j, j - 1} and {k, n - 1, 0, i - 1}. We show that the following two conditions are equivalent: A(P)(H) <= A(P)(H') for all convex n-gons P. c(H)(i, j, k) <= c(H)'(i, J, k) for all convex three-cuts C(i, j, k). From this property, a polynomial time algorithm for determining whether or not given weighted hypergraphs H and H' satisfy "A(P)(H) <= A(P)(H') for all convex n-gons P" is immediately obtained. (c) 2006 Elsevier B.V. All rights reserved.

关键词： hypergraphs convex polygons area convex three-cuts polynomial time algorithms

来源：评论

学校读者我要写书评

暂无评论

A Competitive Two-Agent Scheduling Problem on Parallel Machines with Release Dates and Preemption

引用

MATHEMATICAL PROBLEMS IN ENGINEERING 2013年第1期2013卷 1-5页

作者： Qi, Yawei Wan, Long Jiangxi Univ Finance & Econ Sch Informat Technol Jiangxi Key Lab Data & Knowledge Engn Nanchang 330013 Jiangxi Peoples R China Jiangxi Univ Finance & Econ Sch Informat Technol Nanchang 330013 Jiangxi Peoples R China

We consider a competitive two-agent scheduling problem on multiple identical machines with release dates and preemption. In the scheduling model, there are two agents a and b each having their own job sets J(a) = {J(1)(a),..., J(na)(a)} and J(b) = {J(1)(b),..., J(nb)(b)}, respectively. Each job J(j) epsilon J(a) boolean OR J(b) has a release date r(i) and the n = n(a) + n(b) jobs need to be preemptively scheduled on m identical machines. For m = 2, we show that the trade-off curve of all the Pareto optimal points can be characterized in polynomial time. When m is input, we show that P vertical bar r(j), pmtn vertical bar L-max(a) : L-max(b) < Q can be solved in strongly polynomial time.

关键词： PRODUCTION scheduling PARALLEL computers polynomial time algorithms PROBLEM solving MACHINE theory COMPUTER scheduling

来源：评论

学校读者我要写书评

暂无评论

Two-machine flowshop scheduling problem with coupled-operations

引用

ANNALS OF OPERATIONS RESEARCH 2019年第2期275卷 511-530页

作者： Meziani, Nadjat Oulamara, Ammar Boudhar, Mourad Abderrahmane Mira Univ Bejaia Algeria Univ Lorraine UMR CNRS 75003 LORIA Lab Campus Sci615 Rue Jardin Bot F-54506 Vandoeuvre Les Nancy France USTHB Fac Math RECITS Lab BP 32 Algiers 16111 Algeria

This paper addresses a generalization of the coupled-operations scheduling problem in the context of a flow shop environment. We consider the two-machine scheduling problem with the objective of minimizing the makespan. Each job consists of a coupled-operation to be processed first on the first machine and a single operation to be then processed on the second machine. A coupled-operation contains two operations separated by an exact time delay. The single operation can start on the second machine only when the coupled-operation on the first machine is completed. We prove the NP-completeness of two restricted versions of the general problem, whereas we also exhibit several other well solvable cases.

关键词： Flowshop Coupled-operations Complexity polynomial time algorithms

来源：评论

学校读者我要写书评

暂无评论

CONFORMAL WASSERSTEIN DISTANCE: II. COMPUTATIONAL ASPECTS AND EXTENSIONS

引用

MATHEMATICS OF COMPUTATION 2013年第281期82卷 331-381页

作者： Lipman, Y. Puente, J. Daubechies, I. Weizmann Inst Sci Dept Math & Comp Sci IL-76100 Rehovot Israel Princeton Univ Dept Math Princeton NJ 08544 USA Duke Univ Dept Math Durham NC 27706 USA

This paper is a companion paper to [Yaron Lipman and Ingrid Daubechies, Conformal Wasserstein distances: Comparing surfaces in polynomial time, Adv. in Math. (ELS), 227 (2011), no. 3, 1047-1077, (2011)]. We provide numerical procedures and algorithms for computing the alignment of and distance between two disk-type surfaces. We provide a convergence analysis of the discrete approximation to the arising mass-transportation problems. We furthermore generalize the framework to support sphere-type surfaces, and prove a result connecting this distance to local geodesic distortion. Finally, we perform numerical experiments on several surface datasets and compare them to state-of-the-art methods.

关键词： CONFORMAL geometry polynomial time algorithms APPROXIMATION theory STOCHASTIC convergence DISCRETE geometry NUMERICAL analysis

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：