D. T. Lee and A. K. Lin [2] proved that VERTEX-GUARDING and POINT-GUARDING are NP-hard for simple polygons. We prove that those problems are NP-hard for ortho-polygons, too.

A pool resolution proof is a dag-like resolution proof which admits a depth-first traversal tree in which no variable is used as a resolution variable twice on any branch. The problem of determining whether a given dag-like resolution proof is a valid pool resolution proof is shown to be NP-complete.

We have shown the plausibility of considering time as a Fuzzy concept instead of classical time [7], [8]. By considering time as a fuzzy concept, we will have new classes of Complexity. Here, we show that how some famous problems will be solved in this new picture.

We prove that the problem of determining the minimum propositional proof length is NP- hard to approximate within a factor of 2 log 1 - o(1) n . These results are very robust in that they hold for almost all natural proof systems, including: Frege systems, extended Frege systems, resolution, Horn resolution, the polynomial calculus, the sequent calculus, the cut-free sequent calculus, as well as the polynomial calculus. Our hardness of approximation results usually apply to proof length measured either by (...) number of symbols or by number of inferences, for tree-like or dag-like proofs. We introduce the Monotone Minimum (Circuit) Satisfying Assignment problem and reduce it to the problems of approximation of the length of proofs. (shrink)

Let g be a map defined as the Nisan–Wigderson generator but based on an NP ∩ coNP -function f. Any string b outside the range of g determines a propositional tautology τb expressing this fact. Razborov [27] has conjectured that if f is hard on average for P/poly then these tautologies have no polynomial size proofs in the Extended Frege system EF. We consider a more general Statement that the tautologies have no polynomial size proofs in any propositional proof system. (...) This is equivalent to the statement that the complement of the range of g contains no infinite NP set. We prove that Statement is consistent with Cook' s theory PV and, in fact, with the true universal theory T PV in the language of PV. If PV in this consistency statement could be extended to "a bit" stronger theory then Razborov's conjecture would follow, and if TPV could be added too then Statement would follow. We discuss this problem in some detail, pointing out a certain form of reflection principle for propositional logic, and we introduce a related feasible disjunction property of proof systems. (shrink)

An NP-hardness proof for non-local Multicomponent Tree Adjoining Grammar (MCTAG) by Rambow and Satta (1st International Workshop on Tree Adjoining Grammers 1992 ), based on Dahlhaus and Warmuth (in J Comput Syst Sci 33:456–472, 1986 ), is extended to some linguistically relevant restrictions of that formalism. It is found that there are NP-hard grammars among non-local MCTAGs even if any or all of the following restrictions are imposed: (i) lexicalization: every tree in the grammar contains a terminal; (ii) dominance links: (...) every tree set contains at most two trees, and in every such tree set, there is a link between the foot node of one tree and the root node of the other tree, indicating that the former node must dominate the latter in the derived tree. This is the version of MCTAG proposed in Becker et al. (Proceedings of the 5th conference of the European chapter of the Association for Computational Linguistics 1991 ) to account for German long-distance scrambling. This result restricts the field of possible candidates for an extension of Tree Adjoining Grammar that would be both mildly context-sensitive and linguistically adequate. (shrink)

Local deterministic string-to-string transductions arise in natural language processing (NLP) tasks such as letter-to-sound translation or pronunciation modeling. This class of transductions is a simple generalization of morphisms of free monoids; learning local transductions is essentially the same as inference of certain monoid morphisms. However, learning even a highly restricted class of morphisms, the so-called fine morphisms, leads to intractable problems: deciding whether a hypothesized fine morphism is consistent with observations is an NP-complete problem; and maximizing classification accuracy of the (...) even smaller class of alphabetic substitution morphisms is APX-hard. These theoretical results provide some justification for using the kinds of heuristics that are commonly used for this learning task. (shrink)

In the mid-1970s and early 1980s, several feminist theorists began developing alternatives to the traditional methods of scientific research. The result was a new theory, now recognized as Standpoint Theory, which caused heated debate and radically altered the way research is conducted. The Feminist Standpoint Theory Reader is the first anthology to collect the most important essays on the subject as well as more recent works that bring the topic up-to-date. Leading feminist scholar and one of the founders of Standpoint (...) Theory, Sandra Harding brings together the a prestigious list of scholars--Dorothy Smith, Donna Haraway, Patricia Hill Collins, Nancy Hartsock and Hilary Rose--to not only showcase the most influential essays on the topic but to also highlight subsequent developments of these approaches from a wide variety of disciplines and intellectual and political positions. The Reader will be essential reading for feminist scholars. (shrink)

People in our liberal pluralistic society have conflicting intuitions about the legitimacy of coercive hard paternalism, though respect for agency provides a common source of objection to it. The hard paternalist must give adequate reasons for her coercion which are acceptable to a free and equal agent. Coercion that fails to meet with an agent’s reasonable evaluative commitments is at least problematic and risks being authoritarian. Even if the coercer claims no normative authority over the coercee, the former still uses (...) coercion to replace the latter’s reasons or will with his own reasons or will. But does every hard paternalistic view have to invite such objection? Throughout I will assume that defenders of what I will call “Neutral Paternalism” (NP) and “Commonsense Paternalism” (CP) aim to offer reasons for coercion all can reasonably endorse despite evaluative diversity, in opposition to more objectionable forms of coercive paternalism, such as those which defend it on religious or perfectionist grounds. I will argue, nonetheless, that Gerald Dworkin’s defense of NP and Danny Scoccia’s defense of CP succumb to the same problems of objectionable imposition that saddle other forms of coercive paternalism. The shortcomings in their views suggest that even modest hard paternalism is nonetheless problematic for liberals. (shrink)

We propose a technical reformulation of the measurement problem of quantum mechanics, which is based on the postulate that the final state of a measurement is classical; this accords with experimental practice as well as with Bohr’s views. Unlike the usual formulation (in which the post-measurement state is a unit vector in Hilbert space), our version actually opens the possibility of admitting a purely technical solution within the confines of conventional quantum theory (as opposed to solutions that either modify this (...) theory, or introduce unusual and controversial interpretative rules and/or ontologies). To that effect, we recall a remarkable phenomenon in the theory of Schrödinger operators (discovered in 1981 by Jona-Lasinio, Martinelli, and Scoppola), according to which the ground state of a symmetric double-well Hamiltonian (which is paradigmatically of Schrödinger’s Cat type) becomes exponentially sensitive to tiny perturbations of the potential as ħ→0. We show that this instability emerges also from the textbook wkb approximation, extend it to time-dependent perturbations, and study the dynamical transition from the ground state of the double well to the perturbed ground state (in which the cat is typically either dead or alive, depending on the details of the perturbation). Numerical simulations show that adiabatically arising perturbations may (quite literally) cause the collapse of the wave-function in the classical limit. Thus, at least in the context of a simple mathematical model, we combine the technical and conceptual virtues of decoherence (which fails to solve the measurement problem but launches the key idea that perturbations may come from the environment) with those of dynamical collapse models à la grw (which do solve the measurement problem but are ad hoc), without sharing their drawbacks: single measurement outcomes are obtained (instead of merely diagonal reduced density matrices), and no modification of quantum mechanics is needed. (shrink)

Bd. 1. Aufsätze zur Theorie der Geographie -- Bd. 2. Dimensionen geographischen Denkens.

We exhibit a 10-element semigroup Q such that the question Does a given quasi-identity hold in Q? is co-NP-complete while the question Does a given identity hold in Q? can be answered in linear time.

We exhibit a 10-element semigroup Q such that the question “Does a given quasi-identity hold inQ?” is co-NP-complete while the question “Does a given identity hold inQ?” can be answered in linear time.

Sandra Harding here develops further the themes first addressed in her widely influential book, The Science Question in Feminism, and conducts a compelling analysis of feminist theories on the philosophical problem of how we know what we ...

This article sits at a point of intersection between the philosophy of physics and the metaphysics of modality. There are clear similarities between Everettian quantum mechanics and various modal metaphysical theories, but there have hitherto been few attempts at exploring how the two topics relate. In this article, I build on a series of recent papers by Wilson ([2011], [2012], [2013]), who argues that Everettian quantum mechanics’ connections with traditional modal metaphysics are vital in defending it against objections. I show (...) that Wilson’s preferred version of Everettian quantum mechanics has two problems. First, it is unable to account for the contingency of various intuitively contingent modal claims. Second, it fails to yield intuitive truth values on modal claims about the number of branches in a given Everettian multiverse. Since modal claims about branch number are instrumental in decision-theoretic solutions to Everettian quantum mechanics’ problem(s) with probability, this second problem has wider dialectical implications. I suggest amendments to the underlying metaphysics that overcome these problems. The result is a more robust version of Everettian quantum mechanics. (shrink)

What can contemporary machine learning (ML) models do? Given the proliferation of ML models in society, answering this question matters to a variety of stakeholders, both public and private. The evaluation of models' capabilities is rapidly emerging as a key subfield of modern ML, buoyed by regulatory attention and government grants. Despite this, the notion of an ML model possessing a capability has not been interrogated: what are we saying when we say that a model is able to do something? (...) And what sorts of evidence bear upon this question? -/- In this paper, we aim to answer these questions, using the capabilities of large language models (LLMs) as a running example. Drawing on the large philosophical literature on abilities, we develop an account of ML models' capabilities which can be usefully applied to the nascent science of model evaluation. Our core proposal is a conditional analysis of model abilities (CAMA): crudely, a machine learning model has a capability to X just when it would reliably succeed at doing X if it 'tried'. The main contribution of the paper is making this proposal precise in the context of ML, resulting in an operationalisation of CAMA applicable to LLMs. We then put CAMA to work, showing that it can help make sense of various features of ML model evaluation practice, as well as suggest procedures for performing fair inter-model comparisons. (shrink)

Worries about scientific objectivity seem never-ending. Social critics and philosophers of science have argued that invocations of objectivity are often little more than attempts to boost the status of a claim, while calls for value neutrality may be used to suppress otherwise valid dissenting positions. Objectivity is used sometimes to advance democratic agendas, at other times to block them; sometimes for increasing the growth of knowledge, at others to resist it. Sandra Harding is not ready to throw out objectivity quite (...) yet. For all of its problems, she contends that objectivity is too powerful a concept simply to abandon. In Objectivity and Diversity, Harding calls for a science that is both more epistemically adequate and socially just, a science that would ask: How are the lives of the most economically and politically vulnerable groups affected by a particular piece of research? Do they have a say in whether and how the research is done? Should empirically reliable systems of indigenous knowledge count as "real science"? Ultimately, Harding argues for a shift from the ideal of a neutral, disinterested science to one that prizes fairness and responsibility. (shrink)

This essay is a critical review of Sandra Harding's The Science Question in Feminism. Her text constitutes a monumental effort to capture an overview of recent feminist critique of science and to develop a feminist dialectical and materialist conception of the history of masculinist science. In this analysis of Harding's work, the organizing categories as well as the main assumptions of the text are reconstructed for closer examination within the context of modern feminist critique of science and feminist theory in (...) general. Although a postive review of Harding's text is presented, questions are raised concerning the adequacy of socialist feminist assumptions for such a project, the limitations of Harding's theorization of gender, and the appropriateness of "postmodernism" as a final category of residence. (shrink)

Despite its centrality in the philosophy of cognitive science, there has been little prior philosophical work engaging with the notion of representation in contemporary NLP practice. This paper attempts to fill that lacuna: drawing on ideas from cognitive science, I introduce a framework for evaluating the representational claims made about components of neural NLP models, proposing three criteria with which to evaluate whether a component of a model represents a property and operationalising these criteria using probing classifiers, a popular analysis (...) technique in NLP (and deep learning more broadly). The project of operationalising a philosophically-informed notion of representation should be of interest to both philosophers of science and NLP practitioners. It affords philosophers a novel testing-ground for claims about the nature of representation, and helps NLPers organise the large literature on probing experiments, suggesting novel avenues for empirical research. (shrink)

Feminist epistemologists who attempt to refigure epistemology must wrestle with a number of dualisms. This essay examines the ways Lorraine Code, Sandra Harding, and Susan Hekman reconceptualize the relationship between self/other, nature/culture, and subject/object as they struggle to reformulate objectivity and knowledge.

In _Sciences from Below_, the esteemed feminist science studies scholar Sandra Harding synthesizes modernity studies with progressive tendencies in science and technology studies to suggest how scientific and technological pursuits might be more productively linked to social justice projects around the world. Harding illuminates the idea of multiple modernities as well as the major contributions of post-Kuhnian Western, feminist, and postcolonial science studies. She explains how these schools of thought can help those seeking to implement progressive social projects refine their (...) thinking to overcome limiting ideas about what modernity and modernization are, the objectivity of scientific knowledge, patriarchy, and Eurocentricity. She also reveals how ideas about gender and colonialism frame the conventional contrast between modernity and tradition. As she has done before, Harding points the way forward in _Sciences from Below_. Describing the work of the post-Kuhnian science studies scholars Bruno Latour, Ulrich Beck, and the team of Michael Gibbons, Helga Nowtony, and Peter Scott, Harding reveals how, from different perspectives, they provide useful resources for rethinking the modernity versus tradition binary and its effects on the production of scientific knowledge. Yet, for the most part, they do not take feminist or postcolonial critiques into account. As Harding demonstrates, feminist science studies and postcolonial science studies have vital contributions to make; they bring to light not only the male supremacist investments in the Western conception of modernity and the historical and epistemological bases of Western science but also the empirical knowledge traditions of the global South. _Sciences from Below_ is a clear and compelling argument that modernity studies and post-Kuhnian, feminist, and postcolonial sciences studies each have something important, and necessary, to offer to those formulating socially progressive scientific research and policy. (shrink)

For twenty years, the renowned philosopher of science Sandra Harding has argued that science and technology studies, postcolonial studies, and feminist critique must inform one another. In The Postcolonial Science and Technology Studies Reader, Harding puts those fields in critical conversation, assembling the anthology that she has long wanted for classroom use. In classic and recent essays, international scholars from a range of disciplines think through a broad array of science and technology philosophies and practices. The contributors reevaluate conventional accounts (...) of the West’s scientific and technological projects in the past and present, rethink the strengths and limitations of non-Western societies’ knowledge traditions, and assess the legacies of colonialism and imperialism. The collection concludes with forward-looking essays, which explore strategies for cultivating new visions of a multicultural, democratic world of sciences and for turning those visions into realities. Feminist science and technology concerns run throughout the reader and are the focus of several essays. Harding provides helpful background for each essay in her introductions to the reader’s four sections. Contributors Helen Appleton Karen Bäckstrand Lucille H. Brockway Stephen B. Brush Judith Carney Committee on Women, Population, and the Environment Arturo Escobar Maria E. Fernandez Ward H. Goodenough Susantha Goonatilake Sandra Harding Steven J. Harris Betsy Hartmann Cori Hayden Catherine L. M. Hill John M. Hobson Peter Mühlhäusler Catherine A. Odora Hoppers Consuelo Quiroz Jenny Reardon Ella Reitsma Ziauddin Sardar Daniel Sarewitz Londa Schiebinger Catherine V. Scott Colin Scott Mary Terrall D. Michael Warren. (shrink)

In a recent letter, Dillion et. al (2023) make various suggestions regarding the idea of artificially intelligent systems, such as large language models, replacing human subjects in empirical moral psychology. We argue that human subjects are in various ways indispensable.

According to a view assumed by many scientists and philosophers of science and standardly found in science textbooks, it is controlled ex perience which provides the basis for distinguishing between acceptable and unacceptable theories in science: acceptable theories are those which can pass empirical tests. It has often been thought that a certain sort of test is particularly significant: 'crucial experiments' provide supporting empiri cal evidence for one theory while providing conclusive evidence against another. However, in 1906 Pierre Duhem argued (...) that the falsification of a theory is necessarily ambiguous and therefore that there are no crucial experiments; one can never be sure that it is a given theory rather than auxiliary or background hypotheses which experiment has falsified. w. V. Quine has concurred in this judgment, arguing that "our statements about the external world face the tribunal of sense experience not indi vidually but only as a corporate body". Some philosophers have thought that the Duhem-Quine thesis gra tuitously raises perplexities. Others see it as doubly significant; these philosophers think that it provides a base for criticism of the foundational view of knowledge which has dominated much of western thought since Descartes, and they think that it opens the door to a new and fruitful way to conceive of scientific progress in particular and of the nature and growth of knowledge in general. (shrink)