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

作者： Mohanty, Sidhanth University of California Berkeley

学位级别：Ph.D., Doctor of Philosophy

What makes an algorithmic problem easy or hard? Many general algorithmic techniques arising from decades of research, along with the theory of NP-completeness based on reductions between hard problems, offers a good answer for problems where the input is ``worst-case''. However, this theory has very little to say when the input is random, and comprises of independent samples, as is frequently the case for problems in statistics. Statistical problems seemingly go through abrupt phase transitions in complexity, from hard to easy once the number of samples crosses a threshold. Understanding this boundary between ``hard'' and ``easy'' for statistical problems is still in nascent stages. This thesis comprises recent progress in understanding these phase transitions from the lens of semidefinite programming.

关键词： algorithmic techniques algorithmic problem Semidefinite programming

来源：评论

学校读者我要写书评

暂无评论

Relative order and spectrum in free and related groups

引用

COMMUNICATIONS IN CONTEMPORARY MATHEMATICS 2024年第1期26卷 2250066-2250066页

作者： Delgado, Jordi Ventura, Enric Zakharov, Alexander Univ Basque Country EHU Dept Math Bilbao Spain Univ Politecn Cataluna Dept Matemat Catalonia Spain UPC BarcelonaTech Inst Matemat Catalonia Spain Uniwersytet Wroclawski Inst Matemat Pl Grunwaldzki 2-4 PL-50384 Wroclaw Poland

In this paper, we consider a natural generalization of the concept of order of an element in a group: an element g is an element of G is said to have order k in a subgroup H of G (respectively, in a coset Hu) if k is the first strictly positive integer such that g(k)is an element of H (respectively, g(k)is an element of Hu). We study this notion and its algorithmic properties in the realm of free groups and some related *** positive and negative (algorithmic) results emerge in this setting. On the positive side, among other results, we prove that the order of elements, the set of orders (called spectrum), and the set of preorders (ie the set of elements of a given order) \wrt finitely generated subgroups are always computable in free and free times free-abelian groups. On the negative side, we provide examples of groups and subgroups having essentially any subset of natural numbers as relative spectrum;in particular, non-recursive and even non-recursively enumerable sets of natural numbers. Also, we take advantage of Mikhailova's construction to see that the spectrum membership problem is unsolvable for direct products of nonabelian free groups.

关键词： Order relative order root spectrum subgroup free group Stallings au-tomata algorithmic problem decision problem undecidable problem

来源：评论

学校读者我要写书评

暂无评论

MORTALITY problem AND AFFINE AUTOMATA

引用

CYBERNETICS AND SYSTEMS ANALYSIS 2008年第2期44卷 170-174页

作者： Rystsov, I. K. Natl Tech Univ Ukraine Kiev Polytech Inst Kiev Ukraine

The mortality problem for 2 Chi 2 matrices is treated from the automata theory viewpoint. This problem is shown to be closely related to the reachability problem for linear and affine automata of low dimensions. The d... 详细信息

关键词： mortality problem algorithmic problem linear automaton affine automaton

来源：评论

学校读者我要写书评

暂无评论

algorithmic complexity as a criterion of unsolvability

引用

THEORETICAL COMPUTER SCIENCE 2007年第2-3期383卷 244-259页

作者： Burgin, Mark Univ Calif Los Angeles Dept Math Los Angeles CA 90095 USA

There is a dependency between computability of algorithmic complexity and decidability of different algorithmic problems. It is known that computability of the algorithmic complexity C(x) is equivalent to decidability of the halting problem for Turing machines. Here we extend this result to the realm of superrecursive algorithms, considering algorithmic complexity for inductive Turing machines. We study two types of algorithmic complexity: recursive (classical) and inductive algorithmic complexities. Relations between these types of algorithmic complexity and decidability of algorithmic problems for Turing machines and inductive Turing machines are considered. In particular, it is demonsrated that computability of algorithmic complexity is equivalent not only to decidability of the halting problem, but also to decidability by inductive Turing machines of the first order of many other problems for Turing machines, such as: if a Turing machine computes a recursive (total) function;if a Turing machine gives no result only for n inputs;if a Turing machine gives results only for n inputs. (c) 2007 Elsevier B.V. All rights reserved.

关键词： Kolmogorov complexity recursive algorithmic complexity inductive turing machine algorithmic problem inductive algorithmic complexity decidability super-recursive algorithm

来源：评论

学校读者我要写书评

暂无评论

Superrecursive hierarchies of algorithmic problems

Superrecursive hierarchies of algorithmic problems

引用

International Conference on Foundations of Computer Science (FCS 05)

作者： Burgin, M Univ Calif Los Angeles Dept Comp Sci Los Angeles CA 90095 USA

ISBN: (纸本)1932415718

In this paper, complexity of an algorithmic problem, such as the halting problem for Turing machines, is measured by the classes of automata that are necessary to solve this problem. To classify different problems with respect to their complexity, inductive Turing machines, which extend possibilities Of Turing machines, are used. A hierarchy of inductive Turing machines generates an inductive hierarchy of algorithmic problems. Here we specifically consider algorithmic problems related to Turing machines and ala inductive Turing machines, and find a place for these problems in the inductive hierarchy of algorithmic problems.

关键词： inductive computation algorithmic problem complexity inductive hierarchy algorithmic operation

来源：评论

学校读者我要写书评

暂无评论

algorithmic problem OF RECOGNIZING AUTOMORPHISMS AMONG ENDOMORPHISMS OF FREE ASSOCIATIVE ALGEBRAS OF FINITE RANK