Engaging undergraduate students in the study of ethics and technology is an important and difficult task for both computer science programs and individual instructors. Narratives, especially science fiction, have become a popular way to entice students to deeply engage with ethics topics. We detail experiences across six different institutions of implementing full-semester, part-semester, and single-lecture lessons from the recently-published book Computing and Technology Ethics: Engaging through Science Fiction. We provide an overview of both the book and related instructor materials; explaining how they can be used to effectively teach topics in ethics to undergraduate students in computing and technology development courses. We close by reflecting on how the book was received by students, and general suggestions for implementing ethics education across a range of institutional contexts.

This Birds of a Feather will begin with a high-level overview of the SIGCSE Reads 2024 books and then quickly move to discussion about mentoring students in the era of large language models and ChatGPT, including how students may value the curriculum differently, how learning outcomes may change, and how we can support students and alumni/ae as they work with rapidly changing job and learning expectations. We expect that many of the sessions at SIGCSE will address the radical shifts in learning outcomes and curricular changes due to LLMs. We will not focus on the particulars of these changes, but rather on mentoring in this time with Sister Resisters: Mentoring Black Women on Campus by Janie Victoria Ward and Tracy L. Robinson-Wood as a resource. How do we guide our students through the curriculum upheaval triggered by shifting learning outcomes? How do we help them prepare for the new instantiation of computer science?

This special session furthers the work associated with SIGCSE Reads and the growing community of SIGCSE members who connect to each other through science fiction. This session extends the experiences of earlier sessions by addressing the global and cultural experiences that our students will face in the computing profession through examining works of fiction. The work of the special session will involve diving into the cultural context of this year's SIGCSE Reads stories with discussion about how this experience can be translated to the classroom, with the goal of better preparing students to consider their computing degrees and careers in a pluralistic, global, equitable and just context.

This workshop will introduce participants interested in teaching a full-term computer science ethics course to the tools and techniques of using science fiction to teach that course. The workshop will consist of three hourlong parts, each of which will draw heavily on science fiction as a teaching tool: (1) an introduction to and tips for teaching with multiple ethical frameworks including virtue ethics, deontology, communitarianism, and utilitarianism; (2) A deep dive on teaching about personhood and privacy by focusing on what's at stake, using multiple viewpoints; and (3) an overview and interactive workshop on the practical logistics of teaching a full term ethics course including example syllabi and teaching materials. This course will equip participants to make rich use of science fiction in their course and to incorporate multiple ethical perspectives into classroom discussion. Participants will have an opportunity to work on course structure and teaching modules in small groups and will receive example teaching materials.

This special session furthers the work associated with SIGCSE Reads and the growing community of SIGCSE members who connect to each other through science fiction. This session extends the experiences of earlier sessions by incorporating a new ethical framework, capability ethics, that supports analysis at a societal level rather than a personal level. Updated materials will be available so that the exercise can be translated to other classrooms. Building on an initial description of ethical frameworks and how they have been used with earlier SIGCSE Reads stories, the exercise will be followed by discussion about new stories that provide additional challenges to both teachers and students, with the goal of better preparing students to consider their computing degrees and careers in a pluralistic, global, equitable and just context.

The inclusion of computing ethics and social impact curricula in computer science programs has received increasing attention in research and teaching. While students explicitly interested in the topic may choose to take courses designed only to teach ethical thinking in computer science, we have a societal need to "teach ethics" in a wider variety of computing courses. With the powerful tools that we give students comes responsibility, and students should know how to consider ethical implications of the things they build. The difficulty of developing strategies to "teach ethics" in computing courses is that 1) teaching computing ethics is different than teaching other computational courses, requiring more than the simple transmission of information or knowledge 2) we lack a way to assess the efficacy of the strategies we use to accomplish the "more." We aim to foster a discussion on the current research and instructional approaches, led by researchers who are actively teaching responsible computer science and data science in a variety of institutional settings (e.g., private, public, small, large, etc.). In addition to forming new research and teaching collaborations, we hope this discussion will inspire the larger community of computer science educators to embed computing ethics and social impact in their technical courses.

This special session furthers the work associated with SIGCSE Reads and the growing community of SIGCSE members who connect to each other through science fiction. The goal of this session is to provide a practical experience addressing one of the five common goals presented previously: a learning experience for participants in how science fiction can be used in computing classrooms to teach ethics and develop CS students' facility for considering ethical situations with deeper critical thinking. Materials will be available so that the exercise can be translated to other classrooms. By providing this experience in a virtual format, participants will be able to translate it to their own setting, whether virtual or face-to-face. Building on an initial description of ethical frameworks, the exercise will be followed by discussion about ways to adapt, adjust and modify the exercise to incorporate other fictional works, to fit into a variety of courses, or to address different levels of learners.

We introduce PCP-nets, a formalism to model qualitative conditional preferences with probabilistic uncertainty. PCP-nets generalise CP-nets by allowing for uncertainty over the preference orderings. We define and study both optimality and dominance queries in PCP-nets, and we propose a tractable approximation of dominance which we show to be very accurate in our experimental setting. Since PCP-nets can be seen as a way to model a collection of weighted CP-nets, we also explore the use of PCP-nets in a multi-agent context, where individual agents submit CP-nets which are then aggregated into a single PCP-net. We consider various ways to perform such aggregation and we compare them via two notions of scores, based on well known voting theory concepts. Experimental results allow us to identify the aggregation method that better represents the given set of CP-nets and the most efficient dominance procedure to be used in the multi-agent context.

As is evidenced by the associated AI, Ethics and Society conference, we now take as given the need for ethics education in the AI and general CS curricula. The anticipated surge in AI ethics education will force the field to reckon with delineating and then evaluating learner outcomes to determine what is working and improve what is not. We argue for a more descriptive than normative focus of this ethics education, and propose the development of assessments that can measure descriptive ethical thinking about AI. Such an assessment tool for measuring ethical reasoning capacity in CS contexts must be designed to produce reliable scores for which there is established validity evidence concerning their interpretation and use.

The study of social networks has increased rapidly in the past few decades. Of recent interest are the dynamics of changing opinions over a network. Some research has investigated how interpersonal influence can affect opinion change, how to maximize/minimize the spread of opinion change over a network, and recently, if/how agents can act strategically to effect some outcome in the network's opinion distribution. This latter problem can be modeled and addressed as a reinforcement learning problem; we introduce an approach to help network agents find strategies that outperform hand-crafted policies. Our preliminary results show that our approach is promising in networks with dynamic topologies.

As research into the dynamics and properties of opinion diffusion on social networks has increased, so too has the attention paid to modeling such systems. Simulations using agent-based modeling (ABM) analyze aggregate network outcomes when individual agents act on typically limited information, and tend to focus on agents that are conforming and homophilic - that is, they prefer to be around similar others, and they update their own personal state over time to be more like their friends. In this work, we illustrate the value of diverse agent modeling in environments that allow for strategic unfriending. We focus on network dynamics generated by three agent models, or archetypes. Our work shows that polarization and consensus dynamics, as well as topological clustering effects, may rely more than previously known on the interplay between individuals' goals for the composition of their neighborhood's opinions.

This special session furthers the work associated with SIGCSE Reads and the growing community of SIGCSE members who connect to each other through science fiction. The session starts with a practical experience addressing one of the five common goals presented previously: a learning experience for participants in how science fiction can be used in computing classrooms to teach ethics and develop CS students' facility for considering ethical situations with deeper critical thinking. Materials will be available so that the exercise can be translated to other classrooms. This will be followed by a significant Q & A session with one of this year's authors, Hugo Award winner David D. Levine, whose short story "Damage" addresses questions of ethical decision making by an AI.

The national push for CS departments to teach students to think about ethical implications of their work raises critical questions about how we approach this pedagogically. In contrast to the typical assessments of CS ethical thinking, which have focused on a student's ability to operate successfully within one kind of normative paradigm, our research group advocates for teaching ethics as an ongoing practice that incorporates multiple normative frameworks and an emphasis on the descriptive element of ethical reflection. In this special session, we will discuss the differences between normative and descriptive ethics, practice describing ethical dilemmas, and work together on developing assessment capabilities for descriptive ethical thinking for CS.

We draw on concepts in medical ethics to consider how computer science, and AI in particular, can develop critical tools for thinking concretely about technology's impact on the wellbeing of the people who use it. We focus on patient autonomy---the ability to set the terms of one's encounter with medicine---and on the mediating concepts of informed consent and decisional capacity, which enable doctors to honor patients' autonomy in messy and non-ideal circumstances. This comparative study is organized around a fictional case study of a heart patient with cardiac implants. Using this case study, we identify points of overlap and of difference between medical ethics and technology ethics, and leverage a discussion of that intertwined scenario to offer initial practical suggestions about how we can adapt the concepts of decisional capacity and informed consent to the discussion of technology design.

This special session will allow discussion of how many common goals of CS educators (conveying core CS concepts, creating community for our students, discussing ethics, etc.) can be furthered through the use of literature in CS courses. We will present five goals which are common in CS education, and discuss how incorporating literature relates to them. We will present small case studies showing concrete examples of assignments and courses which have successfully utilized literature in common, core CS courses. We will showcase a Q & A with author Naomi Kritzer, winner of the 2016 Hugo Award for her short story "Cat Pictures Please".

Given the ubiquity of artificial intelligence (AI) in modern societies, it is clear that individuals, corporations, and countries will be grappling with the legal and ethical issues of its use. As global problems require global solutions, we propose the establishment of an international AI regulatory agency that --- drawing on interdisciplinary expertise --- could create a unified framework for the regulation of AI technologies and inform the development of AI policies around the world. We urge that such an organization be developed with all deliberate haste, as issues such as cryptocurrencies, personalized political ad hacking, autonomous vehicles and autonomous weaponized agents are already a reality, affecting international trade, politics, and war.

We argue that it is crucial to the future of AI that our students be trained in multiple complementary modes of ethical reasoning, so that they may make ethical design and implementation choices, ethical career decisions, and that their software will be programmed to take into account the complexities of acting ethically in the world.

The generation of preferences represented as CP-nets for experiments and empirical testing has typically been done in an ad hoc manner that may have introduced a large statistical bias in previous experimental work. We present novel polynomial-time algorithms for generating CP-nets with n nodes and maximum in-degree c uniformly at random. We extend this result to several statistical cultures commonly used in the social choice and preference reasoning literature. A CP-net is composed of both a graph and underlying cp-statements; our algorithm is the first to provably generate both the graph structure and cp-statements, and hence the underlying preference orders themselves, uniformly at random. We have released this code as a free and open source project. We use the uniform generation algorithm to investigate the maximum and expected flipping lengths, i.e., the maximum length over all outcomes o and o', of a minimal proof that o is preferred to o'. Using our new statistical evidence, we conjecture that, for CP-nets with binary variables and complete conditional preference tables, the expected flipping length is polynomial in the number of preference variables. This has positive implications for the usability of CP-nets as compact preference models.

Conditional preference networks (CP-nets) are a commonly studied compact formalism for modeling preferences. To study the properties of CP-nets or the performance of CP-net algorithms on average, one needs to generate CP-nets in an equiprobable manner. We discuss common problems with naive generation, including sampling bias, which invalidates the base assumptions of many statistical tests and can undermine the results of an experimental study. We provide a novel algorithm for provably generating acyclic CP-nets uniformly at random. Our method is computationally efficient and allows for multi-valued domains and arbitrary bounds on the indegree in the dependency graph.

Conditional preference networks (CP-nets) are a mathematical formalism for compactly representing preferences over combinatorial domains. The software package presented allows editing of CP-nets through a graphical interface, loads and saves to an XML-based file format, and detects properties of the currently loaded CP-net.

Did you read any of the common reads for SIGCSE 2015? Now's your chance to talk about them! Three books: I, Robot by Isaac Asimov (Bantam Spectra, 1950), Bellwether by Connie Willis (Bantam Spectra, 1997) and Ready Player One by Ernest Cline (Broadway Books, 2012) were proposed at the end of the 2014 conference. If you're interested in science fiction, whether on a personal, academic, or pedagogical level, come join us in this BoF and discuss one or more of the three suggested books. We'll provide potential topics and discussion questions targeting how to incorporate these books into a CS course, but the discussion will be open. The BoF will close with a discussion of potential books for the 2016 conference.

Positional scoring rules in voting compute the score of an alternative by summing the scores for the alternative induced by every vote. This summation principle ensures that all votes contribute equally to the score of an alternative. We relax this assumption and, instead, aggregate scores by taking into account the rank of a score in the ordered list of scores obtained from the votes. This defines a new family of voting rules, rank-dependent scoring rules (RDSRs), based on ordered weighted average (OWA) operators, which, include all scoring rules, and many others, most of which of new. We study some properties of these rules, and show, empirically, that certain RDSRs are less manipulable than Borda voting, across a variety of statistical cultures.

Are you interested in incorporating some of your favorite science fiction in your classes? Did you know it can help improve student interest in the technical topic? Come join us as we talk about ways to connect SciFi to artificial intelligence, robotics, networking, intellectual property, and other topics. We'll start with overviews of how we've used SciFi and have plenty of time for discussion of new works and old that connect to the material we need to cover, while drawing students into the content and the field.

Asynchronous online discussions are considered the cornerstone of online education. Many instructors of face-to-face courses are "web-enabling" their classes to improve learning through critical inquiry using online discussions. In this exploratory study, we collected and analyzed online discussion data from two dissimilar computer science courses (one technical Graphics for Gaming (G4G) course and a writing intensive Science Fiction and Ethics (SF&E) course). Our findings suggest that, overall, making more posts, posting more questions and engaging in Devil's Advocacy have positive effects on learning, while making more informational posts, explaining to others and making longer posts do not. In the SF&E course, all students perceive that posting helped their learning, while in the G4G course students do not, but posting behavior differentiates those who perform well from those who perform poorly.

The undergraduate computer science curriculum is generally focused on skills and tools; most students are not exposed to much research in the field, and do not learn how to navigate the research literature. We describe how fiction reviews (and specifically science fiction) are used as a gateway to research reviews. Students learn a little about current or recent research on a topic that stirs their imagination, and learn how to search for, read critically, and compare technical papers on a topic related to their chosen science fiction book, movie, or TV show.

A Markov Decision Process (MDP) policy presents, for each state, an action, which preferably maximizes the expected utility accrual over time. In this article, we present a novel explanation system for MDP policies. The system interactively generates conversational English-language explanations of the actions suggested by an optimal policy, and does so in real time. We rely on natural language explanations in order to build trust between the user and the explanation system, leveraging existing research in psychology in order to generate salient explanations. Our explanation system is designed for portability between domains and uses a combination of domain-specific and domain-independent techniques. The system automatically extracts implicit knowledge from an MDP model and accompanying policy. This MDP-based explanation system can be ported between applications without additional effort by knowledge engineers or model builders. Our system separates domain-specific data from the explanation logic, allowing for a robust system capable of incremental upgrades. Domain-specific explanations are generated through case-based explanation techniques specific to the domain and a knowledge base of concept mappings used to generate English-language explanations.

The use of science fiction (SF) to engage students in computer science learning is becoming more popular [1-6]. There is ample material available to help both undergraduate and graduate students make connections between technical content and human experience, from Star Trek to The Hitchhiker's Guide to the Galaxy to 2001: A Space Odyssey to I, Robot and many others. Fiction can be included in technical courses or used to draw students into the field in introductory classes. The panelists, who represent a range of schools, perspectives and classes, will present brief overviews (5-8 minutes) of how they have used science fiction to engage students in technical topics as well as ethical and societal issues related to computing. After the overviews, there will be plenty of time for discussion of examples used within the community and ways to make connections between science fiction and particular classes or topics. We will be gathering additional examples from the discussion and making them available online.

No abstract available.

We investigate the computational complexity of testing dominance and consistency in CP-nets. Previously, the complexity of dominance has been determined for restricted classes in which the dependency graph of the CP-net is acyclic. However, there are preferences of interest that define cyclic dependency graphs; these are modeled with general CP-nets. In our main results, we show here that both dominance and consistency for general CP-nets are PSPACE-complete. We then consider the concept of strong dominance, dominance equivalence and dominance incomparability, and several notions of optimality, and identify the complexity of the corresponding decision problems. The reductions used in the proofs are from STRIPS planning, and thus reinforce the earlier established connections between both areas.

It is known that determinining whether a DEC-POMDP, namely, a cooperative partially observable stochastic game (POSG), has a cooperative strategy with positive expected reward is complete for NEXP. It was not known until now how cooperation affected that complexity. We show that, for competitive POSGs, the complexity of determining whether one team has a positive-expected-reward strategy is complete for the class NEXP with an oracle for NP.

A revision algorithm is a learning algorithm that identifies the target concept, starting from an initial concept. Such an algorithm is considered efficient if its complexity (in terms of the measured resource) is polynomial in the syntactic distance between the initial and the target concept, but only polylogarithmic in the number of variables in the universe. We give efficient revision algorithms in the model of learning with equivalence and membership queries. The algorithms work in a general revision model where both deletion and addition revision operators are allowed. In this model one of the main open problems is the efficient revision of Horn formulas. Two revision algorithms are presented for special cases of this problem: for depth-1 acyclic Horn formulas, and for definite Horn formulas with unique heads.

We present a database framework for the efficient storage and manipulation of interval probability distributions and their associated information. Although work on interval probabilities and on probabilistic databases has appeared before, ours is the first to combine these into a coherent and mathematically sound framework including both standard relational queries and queries based on probability theory. In particular, our query algebra allows users not only to query existing interval probability distributions, but also to construct new ones by means of conditionalization and marginalization, as well as other more common database operations. © 2004 Wiley Periodicals, Inc. Int J Int Syst 19: 789–815, 2004.

We consider the complexity of determining whether differing probability distributions for the same Bayes net, result in different, policies, significantly different, policy outcomes or optimal value functions.

The article describes a novel theoretical framework for uniform storage and management of diverse probabilistic information. The semistructured data model has gained wide acceptance recently as a means of representing data which lacks a rigid structure of schema. In particular, the similarity of the semistructured data model and the underlying data model for eXtensible Markup Language (XML), the emerging open standard for data storage and transmission over the Internet, make our choice of this approach attractive. The authors present the formal model for semistructured probabilistic objects. They provide the theoretical foundations for storing and managing semistructured probabilistic objects. Previously (S. Hawkes and A. Dekhtyar, 2001), we started the process of translating this model into XML. We introduce the advising application and give formal definitions of semistructured probabilistic objects. Finally, we introduce the underlying algebra for semistructured probabilistic databases.

We show that for several variations of partially observable Markov decision processes, polynomial-time algorithms for finding control policies are unlikely to or simply don't have guarantees of finding policies within a constant factor or a constant summand of optimal. Here ``unlikely'' means ``unless some complexity classes collapse,'' where the collapses considered are P=NP, P=PSPACE, or P=EXP. Until or unless these collapses are shown to hold, any control-policy designer must choose between such performance guarantees and efficient computation.

Given a Boolean formula that is not quite right, how does one fix it?That is, if a given formula differs from an unknown target formula, what is the complexity of revising the given formula?The tools available for determining the revisions are queries to membership and equivalence oracles, namely, questions of the form: "Is this an instance of the target formula," and "Is this hypothesis equivalent to the target formula?"In the latter case, if the answer is "No," the oracle returns an instance that is true for exactly one of the hypothesis and the target.For Horn sentences that require only deletion revisions, a revision algorithm is given that is polynomial in the number of clauses of the formula and the minimum number of deletions needed.For 2-term monotone DNF formulas, a revision algorithm is given that is polynomial in the minimum number of necessary deletions and additions and the logarithm of the number of variables.Previous work addressed deletion-only revisions to 2-term unate DNF formulas. WilIEat := VeryBland OR ((NOT vegetables) AND bland AND Meat).Then, though you use the initial theory as a general guide, you happen to observe the preschooler consume a full pound

Controlled stochastic systems occur in science engineering, manufacturing, social sciences, and many other cntexts. If the systems is modeled as a Markov decision process (MDP) and will run ad infinitum , the optimal control policy can be computed in polynomial time using linear programming. The problems considered here assume that the time that the process will run is finite, and based on the size of the input. There are mny factors that compound the complexity of computing the optimal policy. For instance, there are many factors that compound the complexity of this computation. For instance, if the controller does not have complete information about the state of the system, or if the system is represented in some very succint manner, the optimal policy is provably not computable in time polynomial in the size of the input. We analyze the computational complexity of evaluating policies and of determining whether a sufficiently good policy exists for a MDP, based on a number of confounding factors, including the observability of the system state; the succinctness of the representation; the type of policy; even the number of actions relative to the number of states. In almost every case, we show that the decision problem is complete for some known complexity class. Some of these results are familiar from work by Papadimitriou and Tsitsiklis and others, but some, such as our PL-completeness proofs, are surprising. We include proofs of completeness for natural problems in the as yet little-studied classes NP PP .

We survey the complexity of computational problems about Markov decision processes: evaluating policies, finding good and best policies, approximating best policies, and related decision problems.

We examine the computational complexity of testing and finding small plans in probabilistic planning domains with both flat and propositional representations. The complexity of plan evaluation and existence varies with the plan type sought; we examine totally ordered plans, acyclic plans, and looping plans, and partially ordered plans under three natural definitions of plan value. We show that problems of interest are complete for a variety of complexity classes: PL, P, NP, co-NP, PP, NP^PP, co-NP^PP, and PSPACE. In the process of proving that certain planning problems are complete for NP^PP, we introduce a new basic NP^PP-complete problem, E-MAJSAT, which generalizes the standard Boolean satisfiability problem to computations involving probabilistic quantities; our results suggest that the development of good heuristics for E-MAJSAT could be important for the creation of efficient algorithms for a wide variety of problems.

The $\beta$ hierarchy consists of classes $\beta_k={\rm NP}[log kn ]\subseteq {\rm NP}$. Unlike collapses in the polynomial hierarchy and the Boolean hierarchy, collapses in the $\beta$ hierarchy do not seem to translate up, nor does closure under complement seem to cause the hierarchy to collapse. For any consistent set of collapses and separations of levels of the hierarchy that respects ${\rm P} = \beta_1\subseteq \beta_2\subseteq \cdots \subseteq {\rm NP}$, we can construct an oracle relative to which those collapses and separations hold; at the same time we can make distinct levels of the hierarchy closed under computation or not, as we wish. To give two relatively tame examples: for any $k \geq 1$, we construct an oracle relative to which \[ {\rm P} = \beta_{k} \neq \beta_{k+1} \neq \beta_{k+2} \neq \cdots \] and another oracle relative to which \[ {\rm P} = \beta_{k} \neq \beta_{k+1} = {\rm PSPACE}. \] We also construct an oracle relative to which $\beta_{2k} = \beta_{2k+1} \neq \beta_{2k+2}$ for all k.

A language is L-printable if there is a logspace algorithm which, on input 1 n , prints all members in the language of length n. Following the work of Allender and Rubinstein [SIAM J. Comput., 17 (1988), pp. 1193--1202] on P-printable sets, we present some simple properties of the L-printable sets. This definition of "L-printable" is robust and allows us to give alternate characterizations of the L-printable sets in terms of tally sets and Kolmogorov complexity. In addition, we show that a regular or context-free language is L-printable if and only if it is sparse, and we investigate the relationship between L-printable sets, L-rankable sets (i.e., sets A having a logspace algorithm that, on input x, outputs the number of elements of A that precede x in the standard lexicographic ordering of strings), and the sparse sets in L. We prove that under reasonable complexity-theoretic assumptions, these three classes of sets are all different. We also show that the class of sets of small generalized Kolmogorov space complexity is exactly the class of sets that are L-isomorphic to tally languages.

Properties of L-printable sets are considered, and it is shown that two sets A and B that are L-printable and have similar density are L-isomorphic. L-printable sets are characterized as those sets L-isomorphic to tally sets in L, and as subsets of KS[k log n, k log n]. Several classes of L-printable sets are given, including sparse regular and context-free sets; a characterization of sparse regular sets is given. The relationship of the sparse sets in L to the sparse L-rank able and L-printable sets is considered, and strong indications are given that these classes are all different. An oracle is constructed relative to which there are sparse L-rankable sets that are in L and not L-printable, and L-rankable sets of similar density that are not L-isomorphic.

Scalable sets are defined and their properties studied. It is shown that the set of scalable sets is the isomorphism closure of the set of rankable sets and that every scalable set is P-isomorphic to some rankable set. Scalable sets coincide with P-printable sets when sparse, and with P-paddable sets when thick. Using scalability as a tool, the P-isomorphism question for polynomial-time computable sets of similar densities is examined. 1 Introduction This paper defines and investigates the new concept of scalability for polynomial-time sets. A set is scalable if there is an efficient method for computing the number of elements in the set (or its complement) which are less than a given element, relative to some polynomial-time computable and invertible order on \\Sigma . All scalable sets are polynomial-time computable. Scalability generalizes the previously studied concept of ranking which was based on the same property with respect to a fixed ordering, the lexicographic ordering, ...

Classes of machines using very limited amounts of nondeterminism are studied. The $P = ?NP$ question is related to questions about classes lying within P. Complete sets for these classes are given.

In this paper a new property of sets, near-testability, is introduced. A set S is near-testable$(S \in NT)$ if the membership relation for all immediate neighbors is polynomially computable; i.e., if the function $t(x) = \chi _S (x) + \chi _S (x - 1)(\bmod 2)$ is polynomially computable. The near-testable sets form a subclass of the class $ \oplus P$ (parity polynomial time), introduced by Papadimitriou and Zachos, and Goldschlager and Parberry. $ \oplus P$ has a complete set $ \oplus SAT$ that has recently been shown by Valiant and Vazirani to be hard for $NP$ under randomized polynomial-time reductions. It is proved that there is a uniform polynomial one-one reduction that takes every set in $ \oplus P$ to a near-testable set, and it is shown that the image of $ \oplus SAT$ under this reduction (which we call $NTSAT$) is polynomially isomorphic to $ \oplus SAT$. As corollaries it is shown that $NTSAT$ is complete for both $NT$ and for $ \oplus SAT$, that $NTSAT$ is hard for $NP$ under randomized polynomial-time reductions, and that the existence of one-way functions implies the existence of sets that are near-testable but not polynomially decidable. It is then asked whether near-testability is preserved under p-isomorphisms. This leads to a generalization, $NT^ * $, of $NT$ similar to those introduced by Meyer and Paterson and by Ko for self-reducible sets. With this more general definition, $NT^ * $ is shown to be closed under polynomial-time isomorphisms while remaining a subclass of $ \oplus P$. It is conjectured that it is a proper subclass. In fact it is shown that, relative to a random oracle, the containments $P \subseteq NT \subseteq NT^ * \subseteq \oplus P$ are proper with probability one. It is also shown that, relative to a random oracle, with probability one $NT$ and $NT^ * $ are incomparable with both $NP$ and with $coNP$. Finally, the effects that the distribution and density of elements have on the complexity of near-testable sets are considered.

This paper proves three results relating to the isomorphism question for NP-complete sets. Result 1: We construct an oracle A such that SATA is ≤mP- complete for NPA and all ≤mP-complete sets for NPA are pA- isomorphic to SATA. Result 2: We construct a time function T(n) such that DTIME(T(n)) contains btt-complete sets, which are many-one equivalent, but are not p-isomorphic. The proof of this result has two corollaries: 1) There is an oracle, D, such that NPD contains non-p-isomorophic ≤m(D),P-complete sets. 2) There is a ≤mP-degree that contains non-p-isomorphic sets. Result 3: We show that no simple modification of the diagonalization argument used by Ko, Long and Du can be used to produce sets that are both EXPtime-complete w.r.t, polynomial many-one reducibility and not p-isomorphic.