China
Africa
Explore chapters and articles related to this topic
The exact complexity of the Tutte polynomial
Published in Joanna A. Ellis-Monaghan, Iain Moffatt, Handbook of the Tutte Polynomial and Related Topics, 2022
Tomer Kotek, Johann A. Makowsky
We denote by NP the set of decision problems for which it is possible to verify whether a given configuration is correct in polynomial time in the size of the input. We denote by ♯P (pronounced “number P” or “sharp P”) the set of counting problems which count configurations whose correctness can be verified in polynomial time. For example the problem of deciding whether a graph is r-colorable is in NP, and computing the number of r-colorings is in ♯P. Whether P=NP and whether FP=♯P are famous and notoriously difficult open questions in theoretical computer science. A problem X is NP -hard (respectively, ♯P -hard) if using it as an oracle allows one to solve any problem in NP (respectively in ♯P) in polynomial time. Problems which are NP-hard (or ♯P -hard) are provably the hardest problems in NP (respectively ♯P), and are are considered intractable. They are not considered effectively computable, unless NP=P, respectively ♯P=FP.
Experience-Based Constructionism as a Basis for HCI Education: A Case Study
Published in International Journal of Human–Computer Interaction, 2022
Emanuel Felipe Duarte, M. Cecília C. Baranauskas
Regarding the explicit use of constructionist approaches to the teaching of Computer Science, the work of Korte et al. (2007), with first-year Computer Science and Computer Engineering students, report a game-building method for teaching modeling skills in theoretical Computer Science. Even though the subject (finite-state and Turing machines) is initially abstract and theoretical, it leads to new meaning through a direct mapping between the games that the students are building and the models that they are trying to master. The authors argue that besides the benefit of learning by doing a practical task, which may help in understanding a hard to grasp content, such as theoretical Computer Science, a significant element of customization and choice present in the assignment has the potential to increase both motivation and performance among students.
What can we learn from universal Turing machines?
Published in International Journal of Parallel, Emergent and Distributed Systems, 2022
The results of [4] were a long time the best results. Initially appearing in a Soviet journal, Rogozhin [5] was an improved presentation of the results in Theoretical Computer Science, far much accessible. More than 20 years later, Neary and Woods obtained smaller machines, see [6]. As far as the present paper does not aim at giving an account of that race, we will present a small universal Turing machine contained in [6], the machine with four symbols and six states. That machine improves the machine with four symbols and seven states of [5]. That machine, as well as all machines of [4] and [6], is universal in the following meaning: it simulates another system of computation which is able to simulate any Turing machine. The program of the machine is reproduced by Table 2 under a translation of the alphabet to which we turn back in Section 4.
Diagnosability of interconnection networks: past, present and future
Published in International Journal of Parallel, Emergent and Distributed Systems, 2020
Eddie Cheng, Ke Qiu, Zhizhang Shen
These two results bridge the realm of computer engineering to the realm of theoretical computer science/discrete mathematics, thus attracting more researchers to this topic. Earlier researchers consider the problem from two perspectives. The first is to consider this problem for popular interconnection networks. Early papers for this include [11,23–26]. It turns out that all the popular interconnection networks (apart from some boundary cases) have the best possible diagnosability. One of the basic requirements of an interconnection network is for it to be regular, with several notable exceptions such as the mesh. Thus, researchers considered sufficient conditions for regular graphs to have the largest possible diagnosability such as [27,28].